Home/Blog/Interview Prep/Top array interview questions and answers

Top array interview questions and answers

izza ahmad

Dec 25, 2023

14 min read

content

1. Find peak element

Problem statement

Intuition

Code

Explanation

Time and space complexity

2. Sort an array of 0's 1's and 2's

Problem statement

Intuition

Code

Explanation

Time and space complexity

3. Find the missing number

Problem statement

Intuition

Explanation

Time and space complexity

4. Rotating an array by given value

Problem statement

Intuition

Explanation

Time and space complexity

5. Minimum sum subarray of given value k

Problem Statement

Intuition

Explanation

Time and space complexity

6. Two-sum problem

Problem statement

Intuition

Explanation

Time and space complexity

7. Move the zeros to the left

Problem Statement

Intuition

Explanation

Time and space complexity

8. Maximum subarray sum problem

Problem statement

Intuition

Code

Explanation

Time and space complexity

9. Finding k largest elements

Problem Statement

Intuition

Code

Explanation

Time and space complexity

10. Coin change problem

Problem statement

Intuition

Explanation

Time and space complexity

Conclusion

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

Feeling intimidated by coding interviews and uncertain about the types of questions you might face? If you’re short on time to practice data structure questions, you’re in luck. Data structures are a critical component of any coding interview, regardless of the position you’re applying for, and arrays are especially crucial.

In this blog, we’ve got you covered with 10 diverse array problems of varying difficulties that are commonly featured in interview questions. It’s essential to be well-equipped with various strategies, such as the two-pointer technique, sliding window, dynamic programming, Dutch national flag algorithm, subarray problems, and more.

We’ll address problems that incorporate different techniques so that, by the end of this blog, you’ll have knowledge of various optimal strategies to handle not only these problems, but also similar ones you may encounter in interviews. Let’s get started!

1. Find peak element

Problem statement

The problem involves finding the peak number within an array. A peak element is an element that has a value greater than its neighbors on both sides.

public class PeakElement {
    
    private static Integer findPeakElement(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            
            int mid = left + (right - left) / 2;
            
            if (arr[mid] > arr[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (left == arr.length - 1 && arr[left - 1] <= arr[left]) 
                return null;  
                
        return arr[left];
    }
    public static void main(String[] args) {
        int[] myArray = {10, 18, 25, 30, 45, 20, 55, 60, 75, 100};
        System.out.println("The peak element is = " + findPeakElement(myArray)); 
    }
}

Explanation

Two pointers, left and right, are initialized to the starting and ending indices of the array, respectively.
In each iteration, the array is halved and the solution space is reduced using binary search.
The choice of the next half depends on where the peak element resides. This is obtained by first calculating the middle element i.e. mid.
- If the mid is greater than the value on its right, the potential peak will be found within the left half of the array, and the right will then be reduced to mid’s index.
- Otherwise, the mid will be found within the right half, so the left is updated to the index after mid.
Either the peak element (if found) or null (if not found) is returned.

Note: This approach returns the first peak element found if more than one exist.

Time and space complexity

The time complexity of this algorithm is O(log n), as it utilizes the binary search algorithm and halves the solution space each time. Because no extra space is used, the space complexity turns out to be O(1).

2. Sort an array of 0's 1's and 2's

Problem statement

The task revolves around sorting an array that only consists of elements with values of 0, 1, or 2.

public class ArrayOf0s1s2s{
    public static void sortFun(int arr[]) {
        int low = 0;
        int mid = 0;
        int high = arr.length - 1;
        
        while (mid <= high) {
            switch (arr[mid]) {
                case 0:
                    swap(arr, low, mid);
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    swap(arr, mid, high);
                    high--;
                    break;
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] myArr = {1, 0, 2, 1, 0, 2, 1, 2, 0, 1, 1};
        sortFun(myArr);
        System.out.println("The Arrays of 0s 1s and 2's after Sorting = " + java.util.Arrays.toString(myArr));
    }
}

Explanation

Three pointers (low, mid, and high) are set to the start, and end of the array, respectively.
The array is traversed using the mid until it reaches or exceeds the high pointer.
If the value at the mid is 0, we swap elements at low and mid and increment both low and mid.
If the value at the mid is 1, we move the mid pointer forward.
If the value at mid is 2, we swap elements at the mid and high and decrement the high pointer.

Time and space complexity

The time complexity of this algorithm is O(n) as it is traversed once linearly. The space complexity is O(1), as no extra space is used.

3. Find the missing number

Problem statement

The problem involves finding the missing number in an array containing integers from 1 to n. Simply put, the array contains all numbers from 1 to n except one, and we have to find the missing value.

public class MissingNumbers {
    public static int findMissingNumber(int[] arr) {
        int size = arr.length + 1;
        int formula = size * (size + 1) / 2;
        int arraySum = 0;
        for (int num : arr) {
            arraySum += num;
        }
        return formula - arraySum;
    }
    public static void main(String[] args) {
        int myArray[] = {1, 2, 4, 5, 3, 7, 8};
        int missingValue = findMissingNumber(myArray);
        System.out.println("The Missing Value = " + missingValue);
    }
}

Explanation

The size variable is initialized to be one more than the length of the array, since the array needs to contain all numbers from 1 to n except one.
Next, the formula calculates the sum of integers from 1 to n using the above-mentioned formula.
Then, arraySum is used to calculate the sum of the given array by iterating through each element and adding it.
The missing number is then obtained by finding the difference between the calculated sum, using the formula, and the array’s sum arraySum.

Time and space complexity

The time complexity of this algorithm is O(n) as it is traversed once linearly. The space complexity is O(1) as no extra space is used.

4. Rotating an array by given value

Problem statement

The task involves rotating an array to the right by a specified number of positions.

import java.util.Arrays;
public class RotatingArrays {
    public static void rotateArray(int[] arr, int k) {
        int n = arr.length;
        k = k % n;
        reverse(arr, 0, n - 1);          
        reverse(arr, 0, k - 1);        
        reverse(arr, k, n - 1);         
    }
    private static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
    public static void main(String[] args) {
        int[] myArray = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        int givenValue = 4;
        System.out.println("Array before rotation = " + Arrays.toString(myArray));
        rotateArray(myArray, givenValue);
        System.out.println("Array after rotation = " + Arrays.toString(myArray));
    }
}

Explanation

The reverse method takes three parameters—the array arr, and the start and end indices—and reverses this portion of the array.
Then, rotateArray takes the array arr and the given value k, which shows the number of positions to rotate.
We ensure k does not exceed the size of the array using the modulo % operator.
The complete array is reversed, bringing the required number of elements to the front.
The first portion of the array, from index 0 to k - 1, is reversed.
The remaining portion of the array, from index k to the end n - 1, is reversed.

Time and space complexity

The time complexity of this algorithm is O(n), as the array is traversed linearly in the reverse function. The space complexity is O(1), as no extra space is used — only constant variables.

5. Minimum sum subarray of given value k

Problem Statement

The task involves finding a subarrayThe task involves finding a subarray that has a minimum sum in the whole array of integers. The subarray should have a size equal to the value given by the user. that has a minimum sum in the whole array of integers. The subarray should have a size equal to the value given by the user.

public class MinimumSumSubarray {
    public static void minSumFun(int[] arr, int subArraySize) {
        if (arr.length == 0 || arr.length <= subArraySize) {
            return;
        }
        int windowSum = 0;
        int minWindow = Integer.MAX_VALUE;
        int lastIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            windowSum += arr[i];
            if (i + 1 >= subArraySize) {
                if (minWindow > windowSum) {
                    minWindow = windowSum;
                    lastIndex = i;
                }
                windowSum -= arr[i - subArraySize + 1];
            }
        }
        System.out.println("Minimum sum subarray indices = (" + (lastIndex - subArraySize + 1) + ", " + lastIndex + ")");
        for(int i = lastIndex - subArraySize + 1; i <= lastIndex; i++){
            System.out.print(arr[i]);
            System.out.print(" ");
        }
    }
    public static void main(String[] args) {
        int myArray[] = {10, 15, 4, -8, 2, 0, 9, 21};
        int subArraySize = 4;
        minSumFun(myArray, subArraySize);
    }
}

Explanation

The windowSum is created to store the sum of the current window and is initially initialized to zero.
The minWindow stores the minimum sum found overall after considering each window. It’s initially initialized to the maximum possible value so that it can be compared and updated during iterations.
The lastIndex saves the ending index of the subarray holding the sum.
We iterate through the array and update windowSum by adding the current element each time.
When the window size becomes equal to the given subArraySize, we update the windowSum if it is smaller than the current minimum minWindow.
To maintain the size of the window, the first element of the window is subtracted before moving to the next iteration.
At the end of the traversal, the start and end indices are printed. The start index can be found using lastIndex - subArraySize + 1.

Time and space complexity

The time complexity of this algorithm is O(n) due to a linear traversal. The space complexity is O(1) as no extra space is used.

6. Two-sum problem

Problem statement

The task here is to find a pair of elements in a given array that adds up to a specified sum given by the user. If there are two such numbers in the array that add up to the given value, they are returned. We assume that the array is sorted.

Intuition

The solution involves utilizing a two-pointer approach. By initializing two pointers, left at the beginning and right at the end, this algorithm compares the sum of elements at these positions with our required sum.

import java.util.Arrays;
public class TwoSum {
    public static int[] twoSumFun(int[] arr, int requiredSum) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == requiredSum) {
              
                return new int[]{arr[left], arr[right]};
            } else if (sum < requiredSum) {
                left++;
            } else {
                right--;
            }
        }
        return null;
    }
    public static void main(String[] args) {
        int[] myArray = {2, 20, 7, 11, 10, 15};
        
        int ourRequiredSum = 9;
        int[] result = twoSumFun(myArray,ourRequiredSum);
        if (result != null) {
            System.out.println("Sum is found with elements = [" + result[0] + ", " + result[1] + "]");
        } else {
            System.out.println("No pair was found");
        }
    }
}

Explanation

The left pointer is initialized to the first element of the array.
The right pointer is initialized to the last element of the array.
The sum of elements at the left and right indices is computed and saved to sum.
If sum equals requiredSum, the pair is found and returned.
If sum is less than requiredSum, this means a larger sum is needed. The left pointer is therefore incremented to move toward the right.
If sum is greater than requiredSum, this means a smaller sum is needed. The right pointer is therefore decremented.
If we find a pair, it’s returned. If the pointers meet (i.e. the left >= right condition) without finding a pair, null is returned.

Let's dry run for a sum of 7 and an array [1, 2, 3, 4, 5, 6, 7, 8, 9].

Intuition

Due to its specific nature, you can apply an optimal solution that is quicker than a simple sorting algorithm. The Dutch national flag algorithm is the go-to algorithm for such a problem. It separates the array into three parts, each representing one of the values. Three pointers are used to iterate through the array and swap elements among these parts according to their values.

Let's code the algorithm and see how it works!

Intuition

The optimal approach involves utilizing two pointers that keep track of zero and non-zero elements. In the first pass, the non-zero elements are identified and placed at the end of the array. In the second pass, the remaining positions to the left are filled with zeros, since we’ve already placed the non-zero elements at their correct position.

import java.util.Arrays;
public class MoveZerosToLeft {
    public static void moveZerosToLeftFun(int[] arr) {
        int lengthArray = arr.length;
        if (lengthArray < 1) {
            return;
        }
        int writeIdx = lengthArray - 1;
        int readIdx = lengthArray - 1;
        while (readIdx >= 0) {
            if (arr[readIdx] != 0) {
                arr[writeIdx--] = arr[readIdx];
            }
            readIdx--;
        }
        while (writeIdx >= 0) {
            arr[writeIdx--] = 0;
        }
    }
    public static void main(String[] args) {
        int[] myArray = {50, 45, 0, 100, 35, 0, 50, 0, 0, 70, 0};
        System.out.println("Array = " + Arrays.toString(myArray));
        moveZerosToLeftFun(myArray);
        System.out.println("Array after 0's are moved to the left = " + Arrays.toString(myArray));
    }
}

Explanation

Two pointers are created and initialized to the end of the array readIdx and writeIdx.
First, the array is traversed from right to left using readIdx. If the element is non-zero, we move it to writeIdx. This ensures the non-zero elements are moved toward the right and the zeros are overwritten. We decrement both writeIdx and readIdx.
The remaining positions at the left indicate the number of zeros that were present in the array. These positions are then updated to zero. writeIdx is decremented until it reaches the beginning of the array.

Time and space complexity

The time complexity of this algorithm is O(n) as the array is traversed linearly. The space complexity is O(1) as no extra space is used.

8. Maximum subarray sum problem

Problem statement

Our task is to determine the contiguous subarray within a given array that contains the largest sum. A contiguous subarray is a subset of an array containing consecutive elements.

public class KadanesAlgorithm {
    public static int maxSubarraySum(int[] arr) {
        int maxEndingHere = arr[0];
        int maxSoFar = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > (maxEndingHere + arr[i])) {
                maxEndingHere = arr[i];
            } else {
                maxEndingHere = maxEndingHere + arr[i];
            }
            if (maxEndingHere > maxSoFar) {
                maxSoFar = maxEndingHere;
            }
        }
        return maxSoFar;
    }
    public static void main(String[] args) {
        int[] myArray = {-2, 14, -1, 28, -10, 100, -30, 2};
        int maxSum = maxSubarraySum(myArray);
        System.out.println("Maximum subarray sum = " + maxSum);
    }
}

Explanation

Two variables called maxEndingHere and maxSoFar are initialized with the first element’s value in the array.
The algorithm iterates through the array, starting from the second element.
At each step, we check whether or not to add the current element.
If adding the current element results in a larger sum, maxEndingHere is updated.
Otherwise, maxEndingHere is set to the current element (in case the current element was negative and resulted in a lesser sum).
If maxEndingHere surpasses maxSoFar, maxSoFar is updated to store the maximum subarray sum.

Time and space complexity

The time complexity of this algorithm is O(n), as it is traversed once linearly. The space complexity is O(1), as no extra space is used.

9. Finding k largest elements

Problem Statement

The problem revolves around finding a given number of largest values from an array of integers. Let’s say the number is 4, that means we have to find the four largest numbers from the array.

import java.util.PriorityQueue;
public class KLargest{
    private static int[] kLargestElementFun(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int currentElement = arr[i];
           
            if (currentElement > minHeap.peek()) {
                minHeap.poll(); 
                minHeap.offer(currentElement); 
            }
        }
       
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }
     public static void main(String[] args) {
        int[] myArray = {10, 17, 8, 6, 54, 3, 76, 9, 81, 7};
        int k = 3; 
        int[] result = kLargestElementFun(myArray, k);
        System.out.print("K largest elements found = ");
        for (int element : result) {
            System.out.print(element + " ");
        }
    }
}

Explanation

A priority queue minHeap is initialized for the purpose of storing the k largest elements.
We add the first k elements of the array into the minHeap, regardless of their value, using the built-in offer() method.
The remaining array is iterated and each element is compared to the smallest element in the minHeap. The smallest element is obtained using peek().
If the current element being compared is larger than the smallest element in the min-heap, we remove the smallest element using poll() and insert the current value currentElement in minHeap.
After iterating through all elements, the minHeap now contains the k largest elements.

Time and space complexity

The algorithm iterates through the array once, and for each element it performs log(K) operations for insertion and removal in the min-heap. The time complexity turns out to be O(n * log(K)). The space complexity is O(K), as the min-heap stores at most k elements.

10. Coin change problem

Problem statement

In this task we are given an array of possible coin values that we can use and a specific amount. We’re supposed to count the total number of ways we can make change for that amount using the given coins.

public class CoinChange {
    public static int totalWaysForChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1; 
        for (int j = 0; j < coins.length; j++) {
            int coin = coins[j];
            
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5, 7};
        int amount = 11;
        int numWays = totalWaysForChange(coins, amount);
        System.out.println("Total # of ways to make change = " + numWays);
    }
}

Explanation

An array dp is initialized to store the number of ways to make change for each amount.
The dp[0] is initially set to 1 since, for an amount of 0, there is only one way to make change, which is using no coins.
We use coin to represent the value of the current coin being considered.
The dp array is iterated, starting from the value of the current coin to the required amount.
- We use i to represent the current amount being considered.
- The dp[i] represents the number of ways to make change for this amount.
- The dp[i] is updated for each i by adding the number of ways to make change using the current coin. This is done using dp[i] += dp[i - coin], which means for the current amount i, the number of ways to make change includes both the ways without using this coin (dp[i - coin]) and with using this coin (dp[i]).
At the end of the traversal, dp[i] will have the total number of ways to make change for each amount by considering the current coin. Ultimately, the array will be filled for all coins.

For an amount of 5, and possible coin values of 1, 2, and 3, a table like the one below is constructed.

Time and space complexity

The time complexity of this dynamic programming problem is given by O(n * amount), because for each coin we traverse each amount. The space complexity is O(amount), as we use an array to store the number of ways for each amount.

Conclusion

Congratulations! You’re now a master of array questions and can take on all similar questions employing these techniques! Here are a few other questions you can practice to further improve your skills:

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments