Array Programs in Java for Interviews: 25 Problems with Solutions

Q: How do I find duplicate elements in a Java array?

Add each element to a HashSet; if add returns false, it is a duplicate. O(n) time.

Q: How do I solve two sum in O(n)?

Store each value’s index in a HashMap and look up target − value.

25 array problems for Java interviews with brute-force and optimal solutions, complexity for each and real output: second largest, rotation, duplicates, missing number, two sum, Kadane and more.

Ankur Oct 21, 2026 17 min read

These are the 25 array problems that show up again and again in Java interviews. For each one this page gives the idea in a sentence, the brute-force solution where it is worth seeing, the optimal solution, the complexity of both, and the real output of running the code on a small input.

The pattern behind most of them: a nested loop that compares every pair is O(n²); a HashSet, HashMap, a sorted order, two pointers, or a running variable usually turns it into O(n).

#	Problem	Brute force	Best
1	Largest element	—	O(n) time, O(1) space
2	Second largest element	O(n log n) (sort)	O(n)
3	Reverse an array	—	O(n) time, O(1) space
4	Rotate left by k	O(n) time, O(n) space	O(n) time, O(1) space
5	Find duplicate elements	O(n²)	O(n) time, O(n) space
6	Missing number from 1 to n	O(n²)	O(n) time, O(1) space
7	Two sum	O(n²)	O(n) time, O(n) space
8	Maximum subarray sum (Kadane)	O(n²)	O(n) time, O(1) space
9	Remove duplicates from a sorted array	—	O(n) time, O(1) space
10	Move zeroes to the end	—	O(n) time, O(1) space
11	Merge two sorted arrays	—	O(n + m)
12	Check if an array is sorted	—	O(n)
13	Frequency of each element	—	O(n) time, O(k) space for k distinct values
14	Leaders in an array	O(n²)	O(n)
15	Equilibrium index	O(n²)	O(n) time, O(1) space
16	Subarray with a given sum (positive numbers)	O(n²)	O(n)
17	Majority element	O(n²)	O(n) time, O(1) space
18	Intersection of two arrays	O(n×m)	O(n + m)
19	Product of array except self	O(n²)	O(n) time, O(1) extra
20	Sort an array of 0s, 1s and 2s	O(n log n) (sort)	O(n)
21	Best time to buy and sell a stock	O(n²)	O(n)
22	Longest consecutive sequence	O(n log n) (sort)	O(n)
23	Single number (others appear twice)	O(n) with a map	O(n) time, O(1) space
24	Binary search	O(n) linear scan	O(log n)
25	Trapping rain water	O(n²)	O(n) time, O(1) space

Tested on OpenJDK 21.0.12. Run javac ArrayPrograms.java && java ArrayPrograms to reproduce every output line below. Download: ArrayPrograms.java.

The 25 problems

1. Largest element

Track the maximum seen so far.

Brute force	Best
—	O(n) time, O(1) space

static int largest(int[] a) {
    int max = a[0];
    for (int x : a) if (x > max) max = x;
    return max;
}

01 largest            [7, 3, 9, 3, 5, 9, 1] -> 9

Source: ArrayPrograms.java, section a01.

2. Second largest element

Sorting works but is more than needed. Keep two variables, first and second, in one pass. The x != first guard handles duplicates of the maximum: in this input 9 appears twice and the answer is 7.

Brute force	Best
O(n log n) (sort)	O(n)

static int secondLargestBrute(int[] a) {                 // O(n log n): sort, then walk back to the first different value
    int[] c = a.clone();
    Arrays.sort(c);
    for (int i = c.length - 2; i >= 0; i--) if (c[i] != c[c.length - 1]) return c[i];
    throw new NoSuchElementException("all elements equal");
}

static int secondLargest(int[] a) {                      // O(n): one pass, two variables
    int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
    for (int x : a) {
        if (x > first) { second = first; first = x; }
        else if (x > second && x != first) second = x;
    }
    if (second == Integer.MIN_VALUE) throw new NoSuchElementException("all elements equal");
    return second;
}

02 second largest     [7, 3, 9, 3, 5, 9, 1] -> brute 7, one-pass 7

Source: ArrayPrograms.java, section a02.

3. Reverse an array

Swap from both ends towards the middle.

Brute force	Best
—	O(n) time, O(1) space

static void reverse(int[] a) {
    for (int i = 0, j = a.length - 1; i < j; i++, j--) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

03 reverse            [1, 2, 3, 4, 5] -> [5, 4, 3, 2, 1]

Source: ArrayPrograms.java, section a03.

4. Rotate left by k

Copying works in O(n) space. Three reversals (first k, the rest, then everything) rotate in place. See the diagram.

Brute force	Best
O(n) time, O(n) space	O(n) time, O(1) space

static int[] rotateLeftBrute(int[] a, int k) {           // O(n) time, O(n) extra space
    int n = a.length;
    int[] out = new int[n];
    for (int i = 0; i < n; i++) out[i] = a[(i + k) % n];
    return out;
}

static void rotateLeft(int[] a, int k) {                 // O(n) time, O(1) space: three reversals
    int n = a.length;
    k %= n;
    reverseRange(a, 0, k - 1);
    reverseRange(a, k, n - 1);
    reverseRange(a, 0, n - 1);
}

static void reverseRange(int[] a, int i, int j) {
    while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }
}

Source: ArrayPrograms.java.

Each row is the array after one step. The first reversal puts 3 2 1 at the front, the second reverses 4 5 6 7, and the final reversal of everything gives 4 5 6 7 1 2 3, which is the original rotated left by three.

04 rotate left by 3   [1, 2, 3, 4, 5, 6, 7] -> [4, 5, 6, 7, 1, 2, 3] (brute: [4, 5, 6, 7, 1, 2, 3])

Source: ArrayPrograms.java, section a04.

5. Find duplicate elements

Compare every pair, or remember what you have seen in a HashSet.

Brute force	Best
O(n²)	O(n) time, O(n) space

static List<Integer> duplicatesBrute(int[] a) {          // O(n^2)
    List<Integer> out = new ArrayList<>();
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j] && !out.contains(a[i])) out.add(a[i]);
    return out;
}

static List<Integer> duplicates(int[] a) {               // O(n) time, O(n) space
    Set<Integer> seen = new HashSet<>(), dup = new LinkedHashSet<>();
    for (int x : a) if (!seen.add(x)) dup.add(x);
    return new ArrayList<>(dup);
}

05 duplicates         [7, 3, 9, 3, 5, 9, 1] -> brute [3, 9], hash set [3, 9]

Source: ArrayPrograms.java, section a05.

6. Missing number from 1 to n

The sum of 1..n is n(n+1)/2. The shortfall is the missing number. Use long for the sum.

Brute force	Best
O(n²)	O(n) time, O(1) space

static int missingBrute(int[] a, int n) {                // O(n^2): look for every value
    for (int v = 1; v <= n; v++) {
        boolean found = false;
        for (int x : a) if (x == v) { found = true; break; }
        if (!found) return v;
    }
    return -1;
}

static int missing(int[] a, int n) {                     // O(n), O(1): expected sum minus actual sum
    long expected = (long) n * (n + 1) / 2;
    long actual = 0;
    for (int x : a) actual += x;
    return (int) (expected - actual);
}

06 missing 1..6       [1, 2, 4, 5, 6] -> brute 3, sum formula 3

Source: ArrayPrograms.java, section a06.

7. Two sum

For each element, ask the map whether its complement was already seen.

Brute force	Best
O(n²)	O(n) time, O(n) space

static int[] twoSumBrute(int[] a, int target) {          // O(n^2)
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] + a[j] == target) return new int[]{i, j};
    return new int[0];
}

static int[] twoSum(int[] a, int target) {               // O(n): remember what we have seen
    Map<Integer, Integer> index = new HashMap<>();
    for (int i = 0; i < a.length; i++) {
        Integer j = index.get(target - a[i]);
        if (j != null) return new int[]{j, i};
        index.put(a[i], i);
    }
    return new int[0];
}

07 two sum (9)        [2, 7, 11, 15] -> brute [0, 1], hash map [0, 1]

Source: ArrayPrograms.java, section a07.

8. Maximum subarray sum (Kadane)

Best sum of a subarray ending here is either the element alone or the previous best plus it.

Brute force	Best
O(n²)	O(n) time, O(1) space

static int maxSubarrayBrute(int[] a) {                   // O(n^2)
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < a.length; i++) {
        int sum = 0;
        for (int j = i; j < a.length; j++) { sum += a[j]; best = Math.max(best, sum); }
    }
    return best;
}

static int kadane(int[] a) {                             // O(n): best sum of a subarray ending here
    int endingHere = a[0], best = a[0];
    for (int i = 1; i < a.length; i++) {
        endingHere = Math.max(a[i], endingHere + a[i]);  // extend the run, or restart at a[i]
        best = Math.max(best, endingHere);
    }
    return best;
}

08 max subarray       [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> brute 6, Kadane 6

Source: ArrayPrograms.java, section a08.

9. Remove duplicates from a sorted array

Two pointers: read scans, write marks the end of the unique prefix.

Brute force	Best
—	O(n) time, O(1) space

static int removeDuplicatesSorted(int[] a) {             // returns the new length, array edited in place
    if (a.length == 0) return 0;
    int write = 1;
    for (int read = 1; read < a.length; read++) {
        if (a[read] != a[write - 1]) a[write++] = a[read];
    }
    return write;
}

09 dedupe sorted      [1, 1, 2, 2, 2, 3, 4, 4] -> length 4 [1, 2, 3, 4]

Source: ArrayPrograms.java, section a09.

10. Move zeroes to the end

Swap every non-zero into the next write position. Order of non-zeros is preserved.

Brute force	Best
—	O(n) time, O(1) space

static void moveZeroes(int[] a) {
    int write = 0;
    for (int read = 0; read < a.length; read++) {
        if (a[read] != 0) { int t = a[write]; a[write++] = a[read]; a[read] = t; }
    }
}

10 move zeroes        [0, 1, 0, 3, 12] -> [1, 3, 12, 0, 0]

Source: ArrayPrograms.java, section a10.

11. Merge two sorted arrays

Walk both with one index each and take the smaller.

Brute force	Best
—	O(n + m)

static int[] mergeSorted(int[] a, int[] b) {
    int[] out = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length) out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
    while (i < a.length) out[k++] = a[i++];
    while (j < b.length) out[k++] = b[j++];
    return out;
}

11 merge sorted       [1, 4, 7] + [2, 3, 9, 10] -> [1, 2, 3, 4, 7, 9, 10]

Source: ArrayPrograms.java, section a11.

12. Check if an array is sorted

One comparison between neighbours.

Brute force	Best
—	O(n)

static boolean isSorted(int[] a) {
    for (int i = 1; i < a.length; i++) if (a[i - 1] > a[i]) return false;
    return true;
}

12 is sorted          [1, 2, 2, 5] -> true, [3, 1, 2] -> false

Source: ArrayPrograms.java, section a12.

13. Frequency of each element

Map.merge(x, 1, Integer::sum) counts without a null check; LinkedHashMap keeps first-seen order.

Brute force	Best
—	O(n) time, O(k) space for k distinct values

static Map<Integer, Integer> frequency(int[] a) {
    Map<Integer, Integer> freq = new LinkedHashMap<>();
    for (int x : a) freq.merge(x, 1, Integer::sum);
    return freq;
}

13 frequency          [7, 3, 9, 3, 5, 9, 1] -> {7=1, 3=2, 9=2, 5=1, 1=1}

Source: ArrayPrograms.java, section a13.

14. Leaders in an array

Scan from the right, remembering the maximum so far; an element bigger than that is a leader.

Brute force	Best
O(n²)	O(n)

static List<Integer> leaders(int[] a) {                  // an element larger than everything to its right
    LinkedList<Integer> out = new LinkedList<>();
    int max = Integer.MIN_VALUE;
    for (int i = a.length - 1; i >= 0; i--) {
        if (a[i] > max) { max = a[i]; out.addFirst(a[i]); }
    }
    return out;
}

14 leaders            [16, 17, 4, 3, 5, 2] -> [17, 5, 2]

Source: ArrayPrograms.java, section a14.

15. Equilibrium index

Left sum equals right sum. Carry the left sum and derive the right sum as total − left − a[i].

Brute force	Best
O(n²)	O(n) time, O(1) space

static int equilibriumBrute(int[] a) {                   // O(n^2): recompute both sums
    for (int i = 0; i < a.length; i++) {
        int left = 0, right = 0;
        for (int j = 0; j < i; j++) left += a[j];
        for (int j = i + 1; j < a.length; j++) right += a[j];
        if (left == right) return i;
    }
    return -1;
}

static int equilibrium(int[] a) {                        // O(n): carry the left sum, derive the right sum
    int total = 0;
    for (int x : a) total += x;
    int left = 0;
    for (int i = 0; i < a.length; i++) {
        if (left == total - left - a[i]) return i;
        left += a[i];
    }
    return -1;
}

15 equilibrium index  [-7, 1, 5, 2, -4, 3, 0] -> brute 3, one pass 3

Source: ArrayPrograms.java, section a15.

16. Subarray with a given sum (positive numbers)

Sliding window: grow on the right, shrink on the left while the sum is too big. Only valid when all numbers are positive.

Brute force	Best
O(n²)	O(n)

static int[] subarrayWithSum(int[] a, int target) {      // positive numbers only: sliding window, O(n)
    int left = 0, sum = 0;
    for (int right = 0; right < a.length; right++) {
        sum += a[right];
        while (sum > target && left <= right) sum -= a[left++];
        if (sum == target) return new int[]{left, right};
    }
    return new int[0];
}

16 subarray sum 33    [1, 4, 20, 3, 10, 5] -> indexes [2, 4]

Source: ArrayPrograms.java, section a16.

17. Majority element

The element that appears more than n/2 times. Boyer–Moore voting cancels pairs of different elements; the second pass verifies, because a majority may not exist.

Brute force	Best
O(n²)	O(n) time, O(1) space

static int majorityBrute(int[] a) {                      // O(n^2)
    for (int x : a) {
        int count = 0;
        for (int y : a) if (y == x) count++;
        if (count > a.length / 2) return x;
    }
    return -1;
}

static int majority(int[] a) {                           // Boyer-Moore voting, O(n), O(1)
    int candidate = 0, votes = 0;
    for (int x : a) {
        if (votes == 0) candidate = x;
        votes += (x == candidate) ? 1 : -1;
    }
    int count = 0;
    for (int x : a) if (x == candidate) count++;         // verify: a majority may not exist
    return count > a.length / 2 ? candidate : -1;
}

17 majority element   [2, 2, 1, 1, 1, 2, 2] -> brute 2, Boyer-Moore 2; no majority in [1, 2, 3] -> -1

Source: ArrayPrograms.java, section a17.

18. Intersection of two arrays

Put one in a set, filter the other. TreeSet returns sorted unique results.

Brute force	Best
O(n×m)	O(n + m)

static List<Integer> intersection(int[] a, int[] b) {
    Set<Integer> set = new HashSet<>();
    for (int x : a) set.add(x);
    Set<Integer> out = new TreeSet<>();
    for (int y : b) if (set.contains(y)) out.add(y);
    return new ArrayList<>(out);
}

18 intersection       [4, 9, 5, 9] and [9, 4, 9, 8, 4] -> [4, 9]

Source: ArrayPrograms.java, section a18.

19. Product of array except self

No division (division fails on zeros). Pass left to right for prefix products, then right to left multiplying in suffix products.

Brute force	Best
O(n²)	O(n) time, O(1) extra

static int[] productExceptSelf(int[] a) {                // no division, O(n)
    int n = a.length;
    int[] out = new int[n];
    out[0] = 1;
    for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];   // product of everything left of i
    int right = 1;
    for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= a[i]; }
    return out;
}

19 product except self [1, 2, 3, 4] -> [24, 12, 8, 6]

Source: ArrayPrograms.java, section a19.

20. Sort an array of 0s, 1s and 2s

Dutch national flag: low, mid, high pointers partition the array in one pass.

Brute force	Best
O(n log n) (sort)	O(n)

static void sortColors(int[] a) {                        // Dutch national flag: one pass over 0s, 1s and 2s
    int low = 0, mid = 0, high = a.length - 1;
    while (mid <= high) {
        if (a[mid] == 0) { int t = a[low]; a[low++] = a[mid]; a[mid++] = t; }
        else if (a[mid] == 1) mid++;
        else { int t = a[high]; a[high--] = a[mid]; a[mid] = t; }
    }
}

20 sort 0s 1s 2s      [2, 0, 2, 1, 1, 0] -> [0, 0, 1, 1, 2, 2]

Source: ArrayPrograms.java, section a20.

21. Best time to buy and sell a stock

Track the lowest price so far and the best profit from selling today.

Brute force	Best
O(n²)	O(n)

static int maxProfitBrute(int[] p) {                     // O(n^2)
    int best = 0;
    for (int i = 0; i < p.length; i++)
        for (int j = i + 1; j < p.length; j++) best = Math.max(best, p[j] - p[i]);
    return best;
}

static int maxProfit(int[] p) {                          // O(n): track the cheapest price so far
    int min = Integer.MAX_VALUE, best = 0;
    for (int price : p) {
        min = Math.min(min, price);
        best = Math.max(best, price - min);
    }
    return best;
}

21 stock profit       [7, 1, 5, 3, 6, 4] -> brute 5, one pass 5

Source: ArrayPrograms.java, section a21.

22. Longest consecutive sequence

Put everything in a set; only start counting at a number whose predecessor is absent.

Brute force	Best
O(n log n) (sort)	O(n)

static int longestConsecutive(int[] a) {                 // O(n): only start counting at the beginning of a run
    Set<Integer> set = new HashSet<>();
    for (int x : a) set.add(x);
    int best = 0;
    for (int x : set) {
        if (!set.contains(x - 1)) {
            int len = 1;
            while (set.contains(x + len)) len++;
            best = Math.max(best, len);
        }
    }
    return best;
}

22 longest run        [100, 4, 200, 1, 3, 2] -> 4

Source: ArrayPrograms.java, section a22.

23. Single number (others appear twice)

XOR of equal numbers is 0 and XOR with 0 is identity, so duplicates cancel.

Brute force	Best
O(n) with a map	O(n) time, O(1) space

static int singleNumber(int[] a) {                       // every other value appears twice: x ^ x == 0
    int x = 0;
    for (int v : a) x ^= v;
    return x;
}

23 single number      [4, 1, 2, 1, 2] -> 4

Source: ArrayPrograms.java, section a23.

24. Binary search

Halve the range. Compute mid = lo + (hi - lo) / 2 to avoid overflow. Requires a sorted array.

Brute force	Best
O(n) linear scan	O(log n)

static int binarySearch(int[] a, int key) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;                    // not (lo + hi) / 2: that can overflow
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

24 binary search      find 23 -> index 5, find 7 -> -1

Source: ArrayPrograms.java, section a24.

25. Trapping rain water

Water above a bar is min(maxLeft, maxRight) − height. Two pointers compute it without precomputing the maxima.

Brute force	Best
O(n²)	O(n) time, O(1) space

static int trapBrute(int[] h) {                          // O(n^2): water above i = min(maxLeft, maxRight) - h[i]
    int total = 0;
    for (int i = 0; i < h.length; i++) {
        int l = 0, r = 0;
        for (int j = 0; j <= i; j++) l = Math.max(l, h[j]);
        for (int j = i; j < h.length; j++) r = Math.max(r, h[j]);
        total += Math.min(l, r) - h[i];
    }
    return total;
}

static int trap(int[] h) {                               // O(n), O(1): two pointers
    int lo = 0, hi = h.length - 1, lMax = 0, rMax = 0, total = 0;
    while (lo < hi) {
        if (h[lo] < h[hi]) { lMax = Math.max(lMax, h[lo]); total += lMax - h[lo++]; }
        else               { rMax = Math.max(rMax, h[hi]); total += rMax - h[hi--]; }
    }
    return total;
}

25 trapping rain      [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] -> brute 6, two pointers 6

Source: ArrayPrograms.java, section a25.

How to pick the technique

If the problem says…	Reach for
“find a pair / seen before / duplicates”	HashSet or HashMap (problems 5, 7, 18, 22)
“sorted array” or you can sort	Two pointers or binary search (9, 11, 24)
“contiguous subarray”	Kadane, sliding window or prefix sums (8, 16, 15)
“in place, O(1) space”	Swaps and pointers (3, 4, 10, 20)
“everything appears twice except one”	XOR (23)

Common interview questions

What is the difference between Kadane’s algorithm and the brute force for maximum subarray?

Brute force tries every start and end, O(n²). Kadane keeps the best sum ending at each position, O(n).

How do you find the second largest element without sorting?

Keep first and second, updating both in one pass (problem 2).

How do you rotate an array in place?

Three reversals: first k, the rest, then all (problem 4).

Why use lo + (hi - lo) / 2 in binary search?

(lo + hi) / 2 can overflow int when both are large.

When does the sliding-window subarray-sum approach fail?

When the array has negative numbers: shrinking the window no longer reduces the sum monotonically.

Common mistakes

Not handling empty or one-element arrays. a[0] throws on an empty array.
Second largest with duplicates. [9, 9] has no second largest; the code above throws NoSuchElementException rather than returning 9.
Using division for product-except-self. It breaks on zeros.
Overflow in sums. The missing-number program uses long for the sum.
Assuming Boyer–Moore always finds a majority. It returns a candidate; the second pass verifies it.
Mutating the input without saying so. Problems 3, 4, 9, 10 and 20 edit the array in place.

FAQ

What are the most common array programs asked in Java interviews?

Second largest, rotation, duplicates, missing number, two sum, Kadane’s maximum subarray, move zeroes and merge sorted arrays. All are on this page.

How do I find duplicate elements in a Java array?

Add each element to a HashSet; if add returns false, it is a duplicate. O(n) time.

How do I solve two sum in O(n)?

Store each value’s index in a HashMap and look up target − value.

Are these solutions for Java 8 or newer?

They compile on Java 8 and later; I ran them on OpenJDK 21.

Array Programs in Java for Interviews: 25 Problems with Solutions

The 25 problems

How to pick the technique

Common interview questions

Common mistakes

FAQ

What are the most common array programs asked in Java interviews?

How do I find duplicate elements in a Java array?

How do I solve two sum in O(n)?

Are these solutions for Java 8 or newer?

Further reading

Related

No Comments yet!

Leave a ReplyCancel reply