Arrays in java:
- An array is the basic Data Structure that contains items of similar data types.
- There is always an ordering amongst the position of the element.
- It can be accessed with the help of the indices. Java supports 0-indexed arrays. Means the array index starts with 0 in java.
-
We can declare array in java as-
1.int[] arr = new int[size];
2.int[] arr = {1,2,3…};
3.int[] arr = new int[]{1,2,3,...};
In this article we will see some java array programs for interviews that are mostly asked in the java interview.
Java Arrays programs-
1. Given an array arr of size n. Your task is to create the output array based on the input array and the elements will be a multiplication of all the elements in the input array except the value at the current index.
Example -
arr = [4, 9, 6, 8] output = [432, 192, 288, 216]
Explanation -
At index 0, The multiplication of all the elements except 4 is - (9 * 6 * 8) = 432.
At index 1, The multiplication of all the elements except 9 is - (4 * 6 * 8) = 192.
At index 2, The multiplication of all the elements except 6 is - (4 * 9 * 8) = 288.
At index 3, The multiplication of all the elements except 8 is - (4 * 9 * 6) = 216.
Solution -
Approach 1 (Brute Force)
import java.util.Arrays;
class Main {
public static void main(String args[]) {
int[] arr = {4, 9, 6, 8};
int[] output = new int[arr.length];
for(int i = 0; i < arr.length; i++){
int mul = 1;
//Loop for multiplying the values of the array.
for(int j = 0; j < arr.length; j++){
//Skipping the element for the current index
if(i == j)
continue;
mul *= arr[j];
}
//Assigning the values to the current index
output[i] = mul;
}
//Printing the output array.
System.out.print(Arrays.toString(output));
}
}
In this approach, we are assigning the values to the output array for the current index. And each time we are calculating the value to assign to the particular index. This approach takes O(n^2) Time. Because for every index we are calculating the result.
Approach 2 (Optimized)
import java.util.Arrays;
class Main {
public static void main(String args[]) {
int[] arr = {9,6,7,8};
int[] output = new int[arr.length];
int multiply = 1;
//Calculating the multiplication of all the elements.
for(int n : arr)
multiply *= n;
//Assigning to the output array after diving with the
//elements from input array.
for(int i = 0; i < arr.length; i++)
output[i] = multiply / arr[i];
//Printing the output array.
System.out.println(Arrays.toString(output));
}
}
In this approach we are calculating the multiplication of all the elements at first and then assigning the values to the output variable by dividing it by the current indexed element. So we avoid the repetition of work. And we need only 2 individual traversals of the loop. So the time complexity will be O(n).
2. Write a java program to move all the 0 to the end in the array.
Example -
arr = [8, 0, 0, 7, 3, 0, 2] output = [8, 7, 3, 2, 0, 0, 0]
Explanation -
At index 1, there is 0. So 0 will be moved to the last and the first non-zero element will come to the 1st index.
Similarly for index 2 and 5 also.
Solution -
Approach1 (using auxiliary array)
import java.util.Arrays;
class Main {
public static void main(String args[]) {
int[] arr = {8, 0, 0, 7, 3, 0, 2};
int[] output = new int[arr.length];
//Pointer for adding the value in the output array.
int k = 0;
for(int i = 0; i < arr.length; i++){
//Skipping the element if it is 0.
if(arr[i] == 0)
continue;
//Assigning the next value to the output variable.
output[k] = arr[i];
k++;
}
//Printing the output.
System.out.print(Arrays.toString(output));
}
}
In the above approach, we are creating an extra array and adding the non-zero value to the array so the remaining space in the array is filled with 0. The time complexity of this approach is O(n) and Space Complexity is also O(n).
Approach 2 (using 2 pointers)-
import java.util.Arrays;
class Main {
public static void main(String args[]) {
int[] arr = {8, 0, 0, 7, 3, 0, 2};
int i = 0, j = 0;
while(i < arr.length){
//if find 0 then continue until nonzero found.
if(arr[i] == 0){
i++;
}else{
//Swapping the values of 1st non-zero number found after 0
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
j++;
}
}
//Printing the output.
System.out.print(Arrays.toString(arr));
}
}
In the above code we have taken 2 pointers. One will point to the next 0 that needs to be sent to last and another one will be the next element that will replace the index of the first pointer. The time complexity of this will be O(n) and the space complexity will be constant O(1).
3. Write a java program to print the array containing leaders from the given input array. The leader is the element that has all the elements to the right side is less than it.
Example -
arr = [8, 2, 5, 7, 3, 4, 2] output = [2, 4, 7, 8]
Explanation -
We can see 2 is the leader because 2 is the last element in the array. 4 is also the leader because after 4 all the elements are smaller than that. And similarly 7 and 8 also.
Solution -
Approach 1 (Brute Force)
import java.util.ArrayList;
class Main {
public static void main(String args[]) {
int[] arr = {8, 2, 5, 7, 3, 4, 2};
//Creating ArrayList that will contain the leader elements.
ArrayList<Integer> ans = new ArrayList<>();
for(int i = 0; i < arr.length; i++){
boolean flag = true;
//Checking if the particular element is the leader.
for(int j = i+1; j < arr.length; j++){
//If it's not the leader then changing the flag to false
//and break
if(arr[j] > arr[i]){
flag = false;
break;
}
}
//if flag is not false then we know that the element is the
//leader adds in the answer.
if(flag)
ans.add(arr[i]);
}
//Printing the answer.
System.out.println(ans);
}
}
In the above approach we are checking each element if it is leader or not. So the time complexity for the above approach will be O(n2).
Approach 2 (Optimized)-
import java.util.ArrayList;
class Main {
public static void main(String args[]) {
int[] arr = {8, 2, 5, 7, 3, 4, 2};
//Declaring Result array to store the leader element
ArrayList<Integer> ans = new ArrayList<>();
//n represents the length of array size and max will
//store the last element of the array.
int n = arr.length, max = arr[n-1];
ans.add(max);
for(int i = n-2; i >= 0; i--){
//If found another leader then changing the leader
//and add to the answer array.
if(arr[i] > max){
ans.add(arr[i]);
max = arr[i];
}
}
//Printing the leader array.
System.out.print(ans);
}
}
In this approach we are checking the leader from the element and finding the largest. Because that will be the leader as all the smaller elements are on the right side of it. So the time complexity for this approach is O(n).
4. Write a java program to find the index of the peak element in an array. Peak element is greater than its left and right element.
Example -
arr = [4, 5, 7, 1, 2, 3] output = 2
Explanation -
We can see the element at index 2 = (7) is greater than its left and right. Element (5 and 1).
Solution -
class Main {
private static int findPeak(int[] arr, int low, int high){
if(high == low) // Corner case when only a single element is present.
return low;
while(low < high){
//calculating the mid index
int mid = (low + high) / 2;
//checking if the element of mid+1 is the peak
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
//checking if the element of mid-1 is the peak
else if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
//checking if element exists on the left side of array from mid then
//search on left side
else if (arr[low] >= arr[mid])
high = mid - 1;
//checking if element exists on right side of array from mid
//then search on right
else
low = mid + 1;
}
return -1; // returning -1 if element is completely sorted
}
public static void main(String args[]) {
int[] arr = {4, 5, 7, 1, 2, 3};
int peak = findPeak(arr, 0, arr.length-1);
System.out.print(peak);
}
}
5. Given an array consisting of n elements in which every element is appeared at least 2 times, except for the one element. So write a java program to find that element.
Example -
arr = [2,6,8,5,6,7,1,2,5,6,1,1,9,8,9] Output = 7
Explanation -
In the above array, only 7 is the element that occurs only once, So print that element.
Solution -
import java.util.*;
class Main {
public static void main(String args[]) {
HashMap<Integer, Integer> hm = new HashMap<>();
int[] arr = {2,6,8,5,6,7,1,2,5,6,1,1,9,8,9};
//loop to count the frequency of the element in the array.
for(int i : arr){
Object val = hm.get(i);
if(val == null)
val = 0;
//If an element exists then increasing its frequency.
hm.put(i, (int)val+1);
}
for (Map.Entry mapElement : hm.entrySet()) {
int value = (int)mapElement.getValue();
//If found the value appeared only once then break
if(value == 1){
int key = (int)mapElement.getKey();
System.out.println(key);
break;
}
}
}
}
Explanation -
In the above coode, we first calculating the frequency of each element, then after we are checking for the value that appears only once. When the value found, we print that value and break out of the loop as we are sure that there is only 1 element that appears exactly once.
6. Write a program to sort the array using insertion sort.
Example -
arr = [6,3,7,6,2,4,1,8,9] output = [1,2,3,4,6,6,7,8,9]
Solution-
import java.util.Arrays;
public class Main{
//Insertion Sort Algorithm
static void Sort(int A[], int n) {
int j = 0, key = 0;
for (int i = 1; i < n; i++) {
//Choosing an element
key = A[i];
j = i - 1;
//searching for the correct position.
while (j >= 0 && key < A[j]) {
A[j + 1] = A[j--];
}
//Inserting the element to its correct position.
A[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {6,3,7,6,2,4,1,8,9};
Sort(arr, 9);
System.out.println(Arrays.toString(arr));
}
}
Explanation - Insertion sort algorithm picks an element from the array one by one and tries to insert it into its appropriate position in. AAnd exactly that approach we have applied in the above code to sorry the elements on array.
7. Write a java program to search for an element in the array if the elements are sorted and rotated by some k steps.
Example -
arr = [5,6,1,2,3,4] target = 6 Output - Element Found
Arr = [1,3] target = 2 Output - Element Not Found**
Solution -
class Main {
private static boolean search(int[] A, int target) {
int low = 0, high = A.length-1, mid;
while(low <= high){
mid = (low + high)/2;
//Returning mid if target found on mid
if(A[mid] == target) return true;
//Checking if the left subarray is sorted?
if(A[low] <= A[mid]){
//Checking if elements exist between low to mid
if(target >= A[low] && target <= A[mid]){
//if found that element exists in the range so search
//in the left subarray
high = mid-1;
}else{
//if element don't exist between range the search on
//right sub array
low = mid+1;
}
}else{
// checking if target exists in the right subarray range
if(target >= A[mid] && target <= A[high]){
//If element exist in range then search on right subarray
low = mid+1;
}else{
//If elements don't exist in the right subarray then search
// on left subarray
high = mid-1;
}
}
}
return false; //return false if element doesn't exist in array.
}
public static void main(String args[]) {
int[] arr = {6,1,2,3,4,5};
int target = 6;
if(search(arr, target)){
System.out.println(" Element Found. ");
}
else{
System.out.println(" Element not found in array. ");
}
}
}
Explanation - In the above code, we are using binary search approach to search for the element where it should be present. If the elements exist on left from the middle elements and is already sorted, then we binary search for the same. Otherwise we check for the other size if it exist or not.
8. Write a java program to print the kth largest element from an array.
Example -
arr = [5,9,3,7,4,6,1,2,8] k = 3 Output = 7
Explanation - 7 is the 3rd largest element on the array, so we can print this.
Solution -
import java.util.Arrays;
class Main {
public static void main(String args[]) {
int[] arr = {5,9,3,7,4,6,1,2,8};
//Sorting the array
Arrays.sort(arr);
int length = arr.length, k = 3;
//Printing the kth element from last, as that will be the maximum.
System.out.print(arr[length - k]);
}
}
Explanation -
We are sorting the array elements first. We know that in a sorted array the largest element is at the last index. So by using this property, we can fetch the kth largest element by fetching the elements from the last if the elements are sorted.
9. Given an integer array arr and an integer k, reverse the first k element for every 2k element starting from the array. If the last k elements are greater than the length then just skip it.
Example -
arr = [2,9,3,7,5,8,3,4,2,5] k = 2 Output = [9,2,3,7,8,5,3,4,5,2]
arr = [2,7,6,8,5,8,6,2,6,5,9,7,6,3] k = 3 Output = [6,7,2,5,5,8,6,2,6,5,9,7,6,3]
Explanation -
In the output array, we can see that the elements in bold are reversed. Because every kth element we need to reverse. And in the second example, the elements underlined are skipped because they are not the complete k elements.
Solution -
import java.util.Arrays;
class Main {
//method to reverse the elements
private static void reverse(int[] arr, int a, int b){
int temp;
while(a < b){
temp = arr[a];
arr[a++] = arr[b];
arr[b--] = temp;
}
}
public static void main(String args[]) {
int[] arr = {2,7,6,8,5,8,6,2,6,5,9,7,6,3};
int k = 3;
int n = arr.length;
//loop to every kth element and reverse it.
for(int i = 0; i < n-1; i += (k*2)){
int a = i, b = i+k-1;
//Checking if the index exists in between the array length
if(b < b)
reverse(arr, a, b);
else
//Break the loop if no further elements can be reversed.
break;
}
System.out.println(Arrays.toString(arr));
}
}
Explanation -
In the above code, we are traversing through the entire array by twice of k steps. Then finding the index and reversing the element from the array. If the last k index goes out of bound then we terminate the loop and not reverse the array because it's not possible.
10. Write a java program to find the element that appears more than n/2 times from the array. If no element exists that appears more than n/2 times, then print -1.
Example -
arr = [2,2,1,1,1,2,2] Output = 2
arr = [2,3,3,2,5,5,7] Output = -1
Explanation -
In the above input, the size of the array is = 7. And the element that exists more than n/2 (7/2) = 3 is 2. So we need to print element 2.
Similarly in the other example, no element present more than 3 times, so we print -1.
Solution -
import java.util.*;
class Main {
public static void main(String args[]) {
int[] arr = {2,2,1,1,1,2,2};
HashMap<Integer, Integer> hm = new HashMap<>();
int n = arr.length;
//Counting the frequency of the elements.
for(int i : arr){
Object val = hm.get(i);
if(val == null)
val = 0;
hm.put(i, (int)val+1);
}
//flag to check if an element was found or not.
boolean found = false;
for (Map.Entry mapElement : hm.entrySet()) {
int value = (int)mapElement.getValue();
//Checking if such elements exist or not.
if(value > n/2){
int key = (int)mapElement.getKey();
System.out.println(key);
found = true;
break;
}
}
//Printing -1 if element is not found.
if(!found)
System.out.println(-1);
}
}
Explanation -
In the above code we are first creating the frequency of the element and then for each element, we are checking that if the element’s frequency are more than n/2 then we print and break the loop because we know that post n/2 element frequency found, then no element will exist of greater than n/2. At the end, if no element is found of frequency greater than n/2. Then we print -1.
References:
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html
https://www.sanfoundry.com/java-programming-examples-arrays/
https://www.interviewbit.com/java-interview-questions/
ИМХО к каждой задаче стоит добавить решение с Stream API. К первой задаче например так:
Лаконичней ведь :)