Java Array Questions & Solutions
■ Find the maximum and minimum element in an array
int max = arr[0], min = arr[0];
for (int x : arr) {
if (x > max) max = x;
if (x < min) min = x;
}
■ Find the second largest / second smallest element
Arrays.sort(arr);
int secondLargest = arr[arr.length - 2];
int secondSmallest = arr[1];
■ Reverse an array
for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
■ Rotate an array by k positions (right)
Collections.rotate(Arrays.asList(arr), k);
■ Find the sum of elements in an array
int sum = 0;
for (int x : arr) sum += x;
■ Check if an array is sorted
boolean sorted = true;
for (int i = 1; i < arr.length; i++)
if (arr[i] < arr[i-1]) { sorted = false; break; }
■ Implement linear search
int index = -1;
for (int i = 0; i < arr.length; i++)
if (arr[i] == key) { index = i; break; }
■ Implement binary search
int l = 0, r = arr.length - 1, mid;
while (l <= r) {
mid = (l + r) / 2;
if (arr[mid] == key) break;
else if (arr[mid] < key) l = mid + 1;
else r = mid - 1;
}
■ Find the index of the first and last occurrence
int first = -1, last = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key) {
if (first == -1) first = i;
last = i;
}
}
■ Find the kth largest/smallest element
Arrays.sort(arr);
int kthSmallest = arr[k-1];
int kthLargest = arr[arr.length-k];
■ Sort array of 0s, 1s, and 2s (Dutch Flag)
int low=0, mid=0, high=arr.length-1;
while (mid <= high) {
if (arr[mid]==0) swap(arr, low++, mid++);
else if (arr[mid]==1) mid++;
else swap(arr, mid, high--);
}
■ Merge two sorted arrays without extra space
for (int i = arr2.length-1; i >= 0; i--) {
int last = arr1[arr1.length-1], j;
for (j = arr1.length-2; j >= 0 && arr1[j] > arr2[i]; j--)
arr1[j+1] = arr1[j];
if (j != arr1.length-2 || last > arr2[i]) {
arr1[j+1] = arr2[i];
arr2[i] = last;
}
}
■ Maximum subarray sum (Kadane’s Algorithm)
int maxSoFar = arr[0], curr = arr[0];
for (int i = 1; i < arr.length; i++) {
curr = Math.max(arr[i], curr + arr[i]);
maxSoFar = Math.max(maxSoFar, curr);
}
■ Subarray with given sum (positive numbers)
int sum=0, l=0;
for (int r=0; r<arr.length; r++) {
sum += arr[r];
while (sum > target) sum -= arr[l++];
if (sum == target) break;
}
■ Count subarrays with sum = K
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int sum=0,count=0;
for(int x: arr){
sum+=x;
count+=map.getOrDefault(sum-k,0);
map.put(sum,map.getOrDefault(sum,0)+1);
}
■ Longest subarray with 0 sum
Map<Integer,Integer> map = new HashMap<>();
int sum=0,max=0;
for(int i=0;i<arr.length;i++){
sum+=arr[i];
if(sum==0) max=i+1;
if(map.containsKey(sum)) max=Math.max(max,i-map.get(sum));
else map.put(sum,i);
}
■ Longest increasing subsequence (O(n^2))
int[] dp = new int[arr.length];
Arrays.fill(dp,1);
int max=1;
for(int i=1;i<arr.length;i++){
for(int j=0;j<i;j++)
if(arr[i]>arr[j])
dp[i]=Math.max(dp[i],dp[j]+1);
max=Math.max(max,dp[i]);
}
■ Move all zeros to the end
int index=0;
for(int x: arr) if(x!=0) arr[index++]=x;
while(index<arr.length) arr[index++]=0;
■ Find duplicates in array
Set<Integer> set=new HashSet<>();
for(int x: arr){
if(!set.add(x)) System.out.println(x);
}
■ Find missing number (1 to N)
int n = arr.length+1;
int total = n*(n+1)/2;
int sum = 0;
for(int x: arr) sum+=x;
int missing = total - sum;
■ Find majority element (> n/2 times)
int cand=0,count=0;
for(int x: arr){
if(count==0) cand=x;
count+=(x==cand)?1:-1;
}
■ Find equilibrium index
int total=0,left=0;
for(int x: arr) total+=x;
for(int i=0;i<arr.length;i++){
total-=arr[i];
if(left==total) System.out.println(i);
left+=arr[i];
}
■ Leaders in an array
int max=arr[arr.length-1];
System.out.println(max);
for(int i=arr.length-2;i>=0;i--){
if(arr[i]>max){ max=arr[i]; System.out.println(max); }
}
