Array Interview Problems Java Practice

Java Logic Development · Chapter 13 Companion Article

Array Interview Problems

Sixteen classic array interview problems — two-pointer pair and triplet sums, Kadane’s Algorithm, prefix-sum subarrays, Boyer-Moore majority voting, leaders, equilibrium index, peak element, greedy stock trading, and the two water-trapping problems — broken into patterns, dry runs, and working Java programs. The same two-pointer, hashing, prefix-sum, and running-state techniques reappear across sliding-window, dynamic-programming, and greedy interview questions.

Overview

Array interview problems test more than basic looping. They check whether you can recognize patterns such as two pointers, hashing, prefix sums, sliding windows, dynamic programming, greedy logic, and boundary optimization.

Core Techniques Used in This Chapter

Problem	Main Technique	Typical Time
Pair with Given Sum	Sorting + Two Pointers	O(n log n)
Triplet with Given Sum	Sorting + Two Pointers	O(n²)
Two Sum	HashMap	O(n)
Maximum Subarray Sum	Running Sum Analysis	O(n²) basic
Minimum Subarray Sum	Modified Kadane	O(n)
Kadane's Algorithm	Dynamic Programming	O(n)
Subarray with Given Sum	Prefix Sum + HashMap	O(n)
Longest Subarray	Prefix Sum + First Index	O(n)
Maximum Product Subarray	Dynamic Programming	O(n)
Majority Element	Boyer-Moore Voting	O(n)
Leaders in Array	Reverse Traversal	O(n)
Equilibrium Index	Prefix/Suffix Balance	O(n)
Peak Element	Binary Search	O(log n)
Stock Buy and Sell	Greedy Minimum Tracking	O(n)
Trapping Rain Water	Two Pointers	O(n)
Container With Most Water	Two Pointers	O(n)

1. Pair with Given Sum

Problem

Given an integer array and a target value, determine whether any two different elements have a sum equal to the target.

Example:

Input:

Array = [2, 7, 11, 15]
Target = 9

Output:

Pair: 2, 7

Main Idea

After sorting the array, place one pointer at the beginning and another at the end.

For the current pair:

If their sum equals the target, the pair is found.
If the sum is smaller, increase the left pointer.
If the sum is larger, decrease the right pointer.

This works because sorting gives a predictable relationship between pointer movement and the resulting sum.

Java Program

import java.util.Arrays;

public class PairWithGivenSum {
    public static void main(String[] args) {
        int[] arr = {11, 2, 15, 7};
        int target = 9;

        Arrays.sort(arr);

        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) {
                System.out.println("Pair: " + arr[left] + ", " + arr[right]);
                return;
            }

            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println("No pair found");
    }
}

Output

Pair: 2, 7

Dry Run

After sorting:

[2, 7, 11, 15]

First comparison:

2 + 15 = 17

17 is greater than 9, so move the right pointer left.

2 + 11 = 13

Again too large.

2 + 7 = 9

The required pair is found.

Complexity

Sorting: O(n log n)
Two-pointer scan: O(n)
Overall: O(n log n)
Extra space: Depends on the sorting implementation

Edge Cases

Array contains duplicate values.
Target is negative.
Elements are negative.
Array contains fewer than two elements.
Pair uses the same value stored at two different indices.

Common Mistake

Do not allow left and right to point to the same element. The loop condition must be:

left < right

Interview Tip

If the interviewer asks only whether a pair exists and modifying the array is acceptable, sorting plus two pointers is efficient.

If original indices are required, a HashMap-based solution is usually better.

2. Triplet with Given Sum

Problem

Find three different elements whose sum equals a specified target.

Example:

Array = [1, 4, 45, 6, 10, 8]
Target = 22

Possible triplet:

4, 8, 10

Logic

Sort the array first.

Fix one element using index i. Then search the remaining part of the array using two pointers.

The remaining required value is:

target - arr[i]

The left and right pointers try to find two values producing this remaining sum.

Java Program

import java.util.Arrays;

public class TripletWithGivenSum {
    public static void main(String[] args) {
        int[] arr = {1, 4, 45, 6, 10, 8};
        int target = 22;

        Arrays.sort(arr);

        for (int i = 0; i < arr.length - 2; i++) {
            int left = i + 1;
            int right = arr.length - 1;

            while (left < right) {
                int sum = arr[i] + arr[left] + arr[right];

                if (sum == target) {
                    System.out.println("Triplet: " + arr[i] + ", " + arr[left] + ", " + arr[right]);
                    return;
                }

                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        System.out.println("No triplet found");
    }
}

Output

Triplet: 4, 8, 10

Why It Works

Once one element is fixed, the problem becomes a pair-sum problem on the remaining sorted portion.

That reduces a brute-force O(n³) search to O(n²).

Complexity

Sorting: O(n log n)
Outer loop: O(n)
Two-pointer scan for each element: O(n)
Overall: O(n²)

Common Mistake

Starting the left pointer from zero can reuse the already fixed element. It should start from:

i + 1

Interview Variation

You may also be asked to:

Count all valid triplets.
Return unique triplets.
Find a triplet closest to a target.
Handle duplicate values without duplicate results.

3. Two Sum Problem

Problem

Given an array and a target, return the indices of two elements whose values add up to the target.

Unlike the general pair-sum problem, the classic Two Sum problem normally requires original array indices.

Example:

Array = [2, 7, 11, 15]
Target = 9

Output:

Indices: 0, 1

HashMap Approach

For each number, calculate the value needed to complete the target.

complement = target - currentValue

Store previously visited values and their indices in a HashMap.

Before inserting the current value, check whether its complement already exists.

Java Program

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static void main(String[] args) {
        int[] arr = {2, 7, 11, 15};
        int target = 9;

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            int complement = target - arr[i];

            if (map.containsKey(complement)) {
                System.out.println("Indices: " + map.get(complement) + ", " + i);
                return;
            }

            map.put(arr[i], i);
        }

        System.out.println("No solution");
    }
}

Output

Indices: 0, 1

Dry Run

At index 0:

value = 2
complement = 7

7 has not been seen, so store:

2 -> 0

At index 1:

value = 7
complement = 2

2 already exists at index 0.

Therefore:

0, 1

Complexity

Time: O(n) average
Space: O(n)

Why Insert After Checking?

Consider:

[3, 3]
Target = 6

If the current element is stored before checking correctly, careless implementations may accidentally reuse the same index.

Checking first naturally ensures that the matching element came from an earlier index.

Pair Sum vs Two Sum

Pair-sum questions often ask for values or existence.

Two Sum usually asks for original indices, making hashing especially useful.

4. Maximum Subarray Sum

Problem

Find the maximum possible sum of a contiguous section of an array.

For:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

The best subarray is:

[4, -1, 2, 1]

Sum:

A subarray must contain consecutive elements.

Basic Interview Approach

A useful first solution is to choose every possible starting point and extend the subarray toward the right.

Instead of recalculating every sum from scratch, maintain a running sum.

Java Program

public class MaximumSubarraySum {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int maxSum = Integer.MIN_VALUE;

        for (int start = 0; start < arr.length; start++) {
            int currentSum = 0;

            for (int end = start; end < arr.length; end++) {
                currentSum += arr[end];
                maxSum = Math.max(maxSum, currentSum);
            }
        }

        System.out.println("Maximum subarray sum: " + maxSum);
    }
}

Output

Maximum subarray sum: 6

Why Initialize with Integer.MIN_VALUE?

Initializing with zero causes incorrect results when every element is negative.

For:

[-8, -3, -6]

The answer should be:

-3

not zero.

Complexity

Time: O(n²)
Space: O(1)

Optimization

The O(n²) approach clearly demonstrates how subarray boundaries work.

Kadane's Algorithm improves this problem to O(n), which is covered separately later in this chapter.

5. Minimum Subarray Sum

Problem

Find the contiguous subarray having the smallest possible sum.

Example:

[3, -4, 2, -3, -1, 7, -5]

The minimum sum is:

-6

from:

[-4, 2, -3, -1]

Logic

For each position, decide whether to:

start a new subarray from the current value, or
extend the previous minimum-sum subarray.

The decision is:

currentMin = min(arr[i], currentMin + arr[i])

Java Program

public class MinimumSubarraySum {
    public static void main(String[] args) {
        int[] arr = {3, -4, 2, -3, -1, 7, -5};

        int currentMin = arr[0];
        int minSum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            currentMin = Math.min(arr[i], currentMin + arr[i]);
            minSum = Math.min(minSum, currentMin);
        }

        System.out.println("Minimum subarray sum: " + minSum);
    }
}

Output

Minimum subarray sum: -6

Dry Run

Starting values:

currentMin = 3
minSum = 3

At -4:

min(-4, 3 + -4)
min(-4, -1)
currentMin = -4

At 2:

min(2, -4 + 2)
currentMin = -2

At -3:

currentMin = -5

At -1:

currentMin = -6

The smallest value reached is -6.

Complexity

Time: O(n)
Space: O(1)

Interview Connection

This is the reverse form of Kadane's Algorithm.

Maximum Kadane uses Math.max.

Minimum Kadane uses Math.min.

6. Kadane's Algorithm

Purpose

Kadane's Algorithm finds the maximum sum of a contiguous subarray in linear time.

It is one of the most frequently tested array optimization techniques.

Core Decision

At each element, there are only two useful choices:

Start a new subarray from the current element.
Extend the existing subarray.

Therefore:

currentSum = max(arr[i], currentSum + arr[i])

The best value seen so far is stored separately.

Java Program

public class KadanesAlgorithm {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int currentSum = arr[0];
        int maxSum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        System.out.println("Maximum sum: " + maxSum);
    }
}

Output

Maximum sum: 6

Why It Works

Suppose the running sum before the current element is negative.

Adding that negative value would only make the next subarray worse.

It is therefore better to discard the old subarray and start again from the current element.

Kadane's Algorithm performs this decision at every index.

Complexity

Time: O(n)
Space: O(1)

All-Negative Arrays

For:

[-5, -2, -8]

Correct answer:

-2

Initializing both variables using arr[0] correctly handles this case.

A common implementation that resets the sum to zero can incorrectly report zero.

Interview Extensions

An interviewer may ask you to also return:

starting index,
ending index,
actual maximum subarray,
maximum circular subarray sum.

7. Subarray with Given Sum

Problem

Determine whether a contiguous subarray has a sum equal to a target.

Example:

[10, 2, -2, -20, 10]
Target = -10

Valid subarray:

[10, 2, -2, -20]

Why Sliding Window Is Not Always Enough

Sliding window works reliably when array values are non-negative.

If negative numbers are allowed, increasing the window may decrease the sum and shrinking it may increase the sum. The simple sliding-window rule no longer works.

Prefix sums with a HashMap handle both positive and negative numbers.

Prefix Sum Logic

Suppose the current prefix sum is:

prefix

A previous prefix sum of:

prefix - target

means that the elements between those two points sum to target.

Java Program

import java.util.HashMap;
import java.util.Map;

public class SubarrayWithGivenSum {
    public static void main(String[] args) {
        int[] arr = {10, 2, -2, -20, 10};
        int target = -10;

        Map<Integer, Integer> prefixMap = new HashMap<>();
        prefixMap.put(0, -1);

        int prefixSum = 0;

        for (int i = 0; i < arr.length; i++) {
            prefixSum += arr[i];

            int required = prefixSum - target;

            if (prefixMap.containsKey(required)) {
                int start = prefixMap.get(required) + 1;
                System.out.println("Subarray found from index " + start + " to " + i);
                return;
            }

            prefixMap.putIfAbsent(prefixSum, i);
        }

        System.out.println("No subarray found");
    }
}

Output

Subarray found from index 0 to 3

Why Store Prefix Sum 0 at Index -1?

It allows subarrays beginning at index 0 to be detected using the same formula as every other subarray.

Complexity

Time: O(n) average
Space: O(n)

Interview Tip

Ask whether negative values are possible.

That single constraint often determines whether you should use:

Sliding window, or
Prefix sum + HashMap.

8. Longest Subarray

Common Interview Version

The phrase longest subarray usually requires a condition. A very common interview version is:

Find the longest contiguous subarray whose sum equals K.

Example:

[10, 5, 2, 7, 1, 9]
K = 15

Longest valid subarray:

[5, 2, 7, 1]

Length:

Logic

Use prefix sums.

If:

currentPrefix - K

has appeared before, the elements after that earlier position up to the current position have sum K.

To maximize length, keep the first occurrence of each prefix sum.

Java Program

import java.util.HashMap;
import java.util.Map;

public class LongestSubarray {
    public static void main(String[] args) {
        int[] arr = {10, 5, 2, 7, 1, 9};
        int k = 15;

        Map<Integer, Integer> firstIndex = new HashMap<>();
        firstIndex.put(0, -1);

        int prefixSum = 0;
        int maxLength = 0;

        for (int i = 0; i < arr.length; i++) {
            prefixSum += arr[i];

            if (firstIndex.containsKey(prefixSum - k)) {
                int length = i - firstIndex.get(prefixSum - k);
                maxLength = Math.max(maxLength, length);
            }

            firstIndex.putIfAbsent(prefixSum, i);
        }

        System.out.println("Longest length: " + maxLength);
    }
}

Output

Longest length: 4

Why Use putIfAbsent?

For maximum length, the earliest index is the most useful.

Replacing it with a later occurrence would shorten future candidate subarrays.

Complexity

Time: O(n) average
Space: O(n)

Longest subarray can also mean:

longest subarray with sum zero,
longest subarray with equal 0s and 1s,
longest increasing contiguous segment,
longest subarray with at most K distinct values,
longest subarray under a maximum-sum constraint.

Always identify the condition before selecting the technique.

9. Maximum Product Subarray

Problem

Find the maximum product obtainable from a contiguous subarray.

Example:

[2, 3, -2, 4]

Maximum product:

from:

[2, 3]

Why This Is Different from Maximum Sum

Negative numbers create an unusual situation.

A very small negative product can become the largest positive product when multiplied by another negative number.

For this reason, maintain both:

maximum product ending at the current position,
minimum product ending at the current position.

Java Program

public class MaximumProductSubarray {
    public static void main(String[] args) {
        int[] arr = {2, 3, -2, 4};

        int currentMax = arr[0];
        int currentMin = arr[0];
        int result = arr[0];

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < 0) {
                int temp = currentMax;
                currentMax = currentMin;
                currentMin = temp;
            }

            currentMax = Math.max(arr[i], currentMax * arr[i]);
            currentMin = Math.min(arr[i], currentMin * arr[i]);

            result = Math.max(result, currentMax);
        }

        System.out.println("Maximum product: " + result);
    }
}

Output

Maximum product: 6

Why Swap for a Negative Value?

Suppose:

currentMax = 6
currentMin = -12
current = -2

After multiplication:

6 × -2 = -12
-12 × -2 = 24

The previous minimum suddenly becomes the new maximum.

Zero Handling

Zero naturally breaks an existing product chain because:

anything × 0 = 0

The algorithm can restart from subsequent elements.

Complexity

Time: O(n)
Space: O(1)

Common Mistake

Tracking only the maximum product fails when two negative values together create a large positive result.

10. Majority Element

Problem

Find an element that appears more than:

n / 2

times in an array.

Example:

[2, 2, 1, 1, 1, 2, 2]

Majority element:

Boyer-Moore Voting Algorithm

Maintain:

candidate,
count.

Rules:

If count becomes zero, choose the current element as the new candidate.
If the current element equals the candidate, increase count.
Otherwise decrease count.

Java Program

public class MajorityElement {
    public static void main(String[] args) {
        int[] arr = {2, 2, 1, 1, 1, 2, 2};

        int candidate = 0;
        int count = 0;

        for (int value : arr) {
            if (count == 0) {
                candidate = value;
            }

            if (value == candidate) {
                count++;
            } else {
                count--;
            }
        }

        int frequency = 0;

        for (int value : arr) {
            if (value == candidate) {
                frequency++;
            }
        }

        if (frequency > arr.length / 2) {
            System.out.println("Majority element: " + candidate);
        } else {
            System.out.println("No majority element");
        }
    }
}

Output

Majority element: 2

Why Voting Works

Each occurrence of a non-candidate element can cancel one occurrence of the candidate.

If an element truly occupies more than half of the array, all other elements combined cannot completely cancel it.

Why Verify the Candidate?

Boyer-Moore produces a candidate even when no majority element exists.

Example:

[1, 2, 3, 4]

Therefore, if the problem does not guarantee a majority, perform a second pass.

Complexity

Time: O(n)
Space: O(1)

Interview Variation

Finding elements occurring more than n / 3 times requires an extended version with up to two candidates.

11. Leaders in Array

Problem

An element is called a leader if no element to its right is greater than it.

For:

[16, 17, 4, 3, 5, 2]

Leaders are:

17, 5, 2

The last element is always a leader because nothing exists to its right.

Efficient Logic

Scan from right to left.

Maintain the largest value seen so far.

If the current element is greater than or equal to that value, it is a leader.

Java Program

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LeadersInArray {
    public static void main(String[] args) {
        int[] arr = {16, 17, 4, 3, 5, 2};

        List<Integer> leaders = new ArrayList<>();
        int maxFromRight = arr[arr.length - 1];

        leaders.add(maxFromRight);

        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] >= maxFromRight) {
                maxFromRight = arr[i];
                leaders.add(arr[i]);
            }
        }

        Collections.reverse(leaders);

        System.out.println("Leaders: " + leaders);
    }
}

Output

Leaders: [17, 5, 2]

Why Scan from Right?

A brute-force solution checks every element against every value on its right, producing O(n²).

Reverse traversal remembers the maximum right-side value, so each element needs only one comparison.

Complexity

Time: O(n)
Extra space: O(k) for storing k leaders

If only printing leaders from right to left were acceptable, additional collection storage could be avoided.

Equality Rule

Whether equal values count as leaders depends on the definition.

Using:

arr[i] >= maxFromRight

treats equal values as leaders when no strictly greater value exists to their right.

12. Equilibrium Index

Problem

An equilibrium index is a position where:

sum of elements on left = sum of elements on right

For:

[-7, 1, 5, 2, -4, 3, 0]

Index 3 is an equilibrium index.

Left side:

-7 + 1 + 5 = -1

Right side:

-4 + 3 + 0 = -1

Efficient Logic

First calculate the total sum.

Maintain a running left sum.

Before processing index i:

rightSum = totalSum - leftSum - arr[i]

If:

leftSum == rightSum

then i is an equilibrium index.

Java Program

public class EquilibriumIndex {
    public static void main(String[] args) {
        int[] arr = {-7, 1, 5, 2, -4, 3, 0};

        int totalSum = 0;

        for (int value : arr) {
            totalSum += value;
        }

        int leftSum = 0;

        for (int i = 0; i < arr.length; i++) {
            int rightSum = totalSum - leftSum - arr[i];

            if (leftSum == rightSum) {
                System.out.println("Equilibrium index: " + i);
                return;
            }

            leftSum += arr[i];
        }

        System.out.println("No equilibrium index");
    }
}

Output

Equilibrium index: 3

Important Order

Do not add arr[i] into leftSum before performing the comparison.

The current element belongs to neither the left side nor the right side.

Complexity

Time: O(n)
Space: O(1)

Edge Cases

The first index can be an equilibrium index if the sum of everything to its right is zero.

Likewise, the last index qualifies if the left-side sum is zero.

13. Peak Element

Problem

A peak element is not smaller than its neighboring elements.

For:

[1, 3, 20, 4, 1, 0]

20 is a peak.

A peak does not necessarily need to be the maximum element in the entire array.

Binary Search Insight

If:

arr[mid] < arr[mid + 1]

the sequence is rising toward the right, so at least one peak exists on that side.

Otherwise, a peak exists at mid or somewhere to its left.

Java Program

public class PeakElement {
    public static void main(String[] args) {
        int[] arr = {1, 3, 20, 4, 1, 0};

        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        System.out.println("Peak element: " + arr[left]);
        System.out.println("Peak index: " + left);
    }
}

Output

Peak element: 20
Peak index: 2

Why mid + 1 Is Safe

The loop executes only while:

left < right

Therefore mid will always be less than right, making:

arr[mid + 1]

a valid access.

Complexity

Time: O(log n)
Space: O(1)

Interview Detail

A linear search can find a peak in O(n).

The interesting interview challenge is recognizing that the slope of neighboring values allows binary search.

14. Stock Buy and Sell

Problem

Given stock prices where each element represents the price on a particular day, find the maximum profit possible using one buy and one later sell.

Example:

[7, 1, 5, 3, 6, 4]

Best transaction:

Buy at 1
Sell at 6

Profit:

Logic

While moving from left to right:

Track the lowest price seen so far.
Calculate the profit if stock were sold today.
Keep the highest profit.

The selling day automatically occurs after the tracked buying day.

Java Program

public class StockBuyAndSell {
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};

        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            int profit = prices[i] - minPrice;
            maxProfit = Math.max(maxProfit, profit);
            minPrice = Math.min(minPrice, prices[i]);
        }

        System.out.println("Maximum profit: " + maxProfit);
    }
}

Output

Maximum profit: 5

Dry Run

Prices:

7, 1, 5, 3, 6, 4

Lowest price eventually becomes:

Potential profits include:

5 - 1 = 4
3 - 1 = 2
6 - 1 = 5
4 - 1 = 3

Maximum:

Complexity

Time: O(n)
Space: O(1)

Falling Price Case

For:

[7, 6, 4, 3, 1]

No profitable transaction exists.

The program returns:

Interview Variations

Clarify whether the question allows:

one transaction,
unlimited transactions,
at most two transactions,
transaction fees,
cooldown days.

Each version requires different logic.

15. Trapping Rain Water

Problem

Given bar heights, calculate how much rain water can be trapped between them.

Example:

[4, 2, 0, 3, 2, 5]

Total trapped water:

Basic Formula

Water above an index depends on the smaller of:

highest wall on the left,
highest wall on the right.

Therefore:

water = min(leftMax, rightMax) - height

Instead of storing complete left-max and right-max arrays, two pointers can solve the problem using constant extra space.

Java Program

public class TrappingRainWater {
    public static void main(String[] args) {
        int[] height = {4, 2, 0, 3, 2, 5};

        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int water = 0;

        while (left < right) {
            if (height[left] <= height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }

        System.out.println("Trapped water: " + water);
    }
}

Output

Trapped water: 9

Why Process the Smaller Side?

Suppose:

height[left] <= height[right]

The right side already provides a boundary at least as high as the current left bar.

Therefore, the amount of water determined by the left maximum can safely be calculated without knowing every future right-side bar.

The same reasoning applies symmetrically when the right side is smaller.

Complexity

Time: O(n)
Space: O(1)

Cases Producing Zero Water

Strictly increasing:

[1, 2, 3, 4]

Strictly decreasing:

[4, 3, 2, 1]

Flat:

[3, 3, 3]

None contains a valley enclosed by higher boundaries.

Common Mistake

Do not calculate water using only neighboring bars. Water at a position depends on the highest boundaries on both sides, not merely immediate neighbors.

16. Container With Most Water

Problem

Each array element represents the height of a vertical line.

Choose two lines that can hold the greatest amount of water.

For:

[1, 8, 6, 2, 5, 4, 8, 3, 7]

Maximum area:

Area Formula

For indices left and right:

width = right - left

Container height is limited by the shorter line:

height = min(arr[left], arr[right])

Therefore:

area = width × height

Two-Pointer Logic

Begin with the widest possible container.

After calculating its area, move the pointer pointing to the shorter line.

Why?

Moving the taller line decreases width while the same shorter line still limits the height. That cannot produce a better container because of that unchanged height limitation.

Moving the shorter line gives a chance to discover a taller limiting boundary.

Java Program

public class ContainerWithMostWater {
    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};

        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int width = right - left;
            int containerHeight = Math.min(height[left], height[right]);
            int area = width * containerHeight;

            maxArea = Math.max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println("Maximum area: " + maxArea);
    }
}

Output

Maximum area: 49

Dry Run of Best Pair

The best pair occurs using:

index 1 -> height 8
index 8 -> height 7

Width:

8 - 1 = 7

Usable height:

min(8, 7) = 7

Area:

7 × 7 = 49

Complexity

Time: O(n)
Space: O(1)

Trapping Rain Water vs Container With Most Water

These two problems look similar because both involve heights and water, but their objectives are different.

Trapping Rain Water

Calculates water stored above multiple internal positions.

Example concept:

wall | water | wall

Water may accumulate in many valleys.

Container With Most Water

Selects exactly two vertical lines and calculates one rectangular container.

Area depends on:

distance × shorter height

Do not apply the rain-water formula to the container problem.

Important Interview Patterns from These Problems

Two Pointers

Useful when two boundaries move based on comparisons.

Covered by:

Pair with Given Sum
Triplet with Given Sum
Trapping Rain Water
Container With Most Water

Two pointers are especially useful when the array is sorted or when decisions can safely eliminate one boundary.

Hashing

Useful when the question repeatedly asks:

Have I already seen a value related to the current value?

Covered by:

Two Sum
Subarray with Given Sum
Longest Subarray with Sum K

Hashing often exchanges additional O(n) space for O(n) average time.

Prefix Sum

Prefix sums convert repeated range-sum calculations into differences between cumulative sums.

If:

prefix[i] = sum from index 0 through i

then a subarray sum can be derived from two prefix values.

This technique is particularly powerful when negative values prevent a normal sliding-window solution.

Dynamic Programming with Running State

Some array problems do not need a full dynamic-programming table.

Only the previous state is required.

Examples:

Kadane's Algorithm
Minimum Subarray Sum
Maximum Product Subarray

This reduces space to O(1).

Greedy Decisions

A greedy solution makes the best useful decision at the current position without revisiting earlier choices.

Examples:

Stock Buy and Sell
Boyer-Moore Majority Element
Two-pointer container movement

The important interview skill is explaining why the discarded choice can never produce a better answer.

Common Array Interview Mistakes

1. Confusing Subarray and Subsequence

A subarray must be contiguous.

For:

[1, 2, 3, 4]

Valid subarray:

[2, 3]

Not a subarray:

[1, 3, 4]

The second selection skips index 1.

2. Ignoring Negative Numbers

Negative values affect several common techniques.

A simple sliding window that works for positive values may fail when negatives are allowed.

3. Initializing Maximum Values to Zero

For all-negative arrays, zero may not be a valid answer.

Prefer initialization from the first array element when the problem requires a non-empty subarray.

4. Forgetting Integer Overflow

Expressions such as:

arr[i] + arr[j]

or:

width * height

may overflow int when constraints are very large.

For large input limits, use long.

Example:

long area = (long) width * containerHeight;

5. Returning Values Instead of Indices

Read the requirement carefully.

Two Sum commonly requires indices, while pair-sum questions may ask for the actual values.

6. Modifying the Original Array

Sorting changes array order.

If the original positions matter, avoid sorting unless you preserve the original indices separately.

7. Using O(n²) When an O(n) Pattern Exists

A brute-force solution is useful for explaining the problem, but interviewers usually expect optimization when input size is large.

Look for:

HashMap
prefix sum
two pointers
greedy tracking
Kadane's Algorithm
binary search

Choosing the Correct Technique

Clue in Question	Technique to Consider
Find two values producing target	Hashing or Two Pointers
Sorted array with pair condition	Two Pointers
Three values producing target	Sort + Fixed Element + Two Pointers
Continuous range sum	Prefix Sum / Sliding Window
Negative values with target sum	Prefix Sum + HashMap
Maximum contiguous sum	Kadane's Algorithm
Maximum contiguous product	Track Maximum and Minimum
More than half frequency	Boyer-Moore
Left-side and right-side sums	Prefix/Suffix reasoning
Local maximum in array	Binary Search
Best single stock transaction	Greedy minimum tracking
Boundaries closing from both ends	Two Pointers

Sliding Window vs Prefix Sum

These approaches are often confused.

Sliding Window

Best suited to situations where moving the window has predictable effects.

For example, when all values are positive:

adding an element increases the sum,
removing an element decreases the sum.

That makes window adjustment reliable.

Prefix Sum

More flexible when values may be negative.

For:

[5, -10, 20]

Adding an element can decrease or increase the sum unpredictably.

Prefix-sum mathematics does not depend on monotonic behavior, so it remains valid.

Pair Sum vs Two Sum

These names are often used interchangeably, but interview requirements may differ.

Pair with Given Sum

Usually asks:

Does a pair exist?
Print the pair.
Count pairs.
Print unique pairs.

Sorting plus two pointers is often appropriate.

Two Sum

The classic version usually asks:

Return the original indices of two numbers.

A HashMap is usually preferred because sorting would destroy the direct connection to original indices.

Kadane's Algorithm vs Maximum Product Subarray

Both maintain information about subarrays ending at the current index, but their states are different.

Maximum Sum

Only the best current sum is needed:

current = max(value, current + value)

Maximum Product

Both maximum and minimum products are required because:

negative × negative = positive

A minimum negative product may become the next maximum positive product.

Trapping Rain Water vs Container With Most Water

Both involve vertical heights but solve fundamentally different problems.

Feature	Trapping Rain Water	Container With Most Water
Goal	Total trapped water	Maximum single container area
Uses internal bars	Yes	No
Uses two selected boundaries only	No	Yes
Main reasoning	Left and right maximum	Width and shorter height
Optimal time	O(n)	O(n)

Interview Complexity Summary

Problem	Time	Extra Space
Pair with Given Sum	O(n log n)	Depends on sort
Triplet with Given Sum	O(n²)	Depends on sort
Two Sum	O(n) average	O(n)
Maximum Subarray Sum Basic	O(n²)	O(1)
Minimum Subarray Sum	O(n)	O(1)
Kadane's Algorithm	O(n)	O(1)
Subarray with Given Sum	O(n) average	O(n)
Longest Subarray with Sum K	O(n) average	O(n)
Maximum Product Subarray	O(n)	O(1)
Majority Element	O(n)	O(1)
Leaders in Array	O(n)	O(k) for result
Equilibrium Index	O(n)	O(1)
Peak Element	O(log n)	O(1)
Stock Buy and Sell	O(n)	O(1)
Trapping Rain Water	O(n)	O(1)
Container With Most Water	O(n)	O(1)

Practical Interview Checklist

Before coding an array interview problem, identify these points:

Is the required range contiguous?
Does the question need values or original indices?
Is the array sorted?
Can it contain negative numbers?
Can it contain duplicates?
Is one result required or all results?
Can the original array be modified?
What are the input-size constraints?
Can integer arithmetic overflow?
Is O(n²) acceptable, or is O(n) or O(log n) expected?
Can hashing reduce repeated searching?
Can sorting enable two-pointer movement?
Can prefix sums convert a range condition into a lookup?
Can a running state replace nested loops?
Can one side of the search space be safely discarded?

Recognizing the correct pattern before writing Java code is usually the main difference between a basic solution and an interview-ready solution.

Overview

Core Techniques Used in This Chapter

1. Pair with Given Sum

Problem

Main Idea

Java Program

Output

Dry Run

Complexity

Edge Cases

Common Mistake

Interview Tip

2. Triplet with Given Sum

Problem

Logic

Java Program

Output

Why It Works

Complexity

Common Mistake

Interview Variation

3. Two Sum Problem

Problem

HashMap Approach

Java Program

Output

Dry Run

Complexity

Why Insert After Checking?

Pair Sum vs Two Sum

4. Maximum Subarray Sum

Problem

Basic Interview Approach

Java Program

Output

Why Initialize with Integer.MIN_VALUE?

Complexity

Optimization

5. Minimum Subarray Sum

Problem

Logic

Java Program

Output

Dry Run

Complexity

Interview Connection

6. Kadane's Algorithm

Purpose

Core Decision

Java Program

Output

Why It Works

Complexity

All-Negative Arrays

Interview Extensions

7. Subarray with Given Sum

Problem

Why Sliding Window Is Not Always Enough

Prefix Sum Logic

Java Program

Output

Why Store Prefix Sum 0 at Index -1?

Complexity

Interview Tip

8. Longest Subarray

Common Interview Version

Logic

Java Program

Output

Why Use putIfAbsent?

Complexity

Related Interview Variations

9. Maximum Product Subarray

Problem

Why This Is Different from Maximum Sum

Java Program

Output

Why Swap for a Negative Value?

Zero Handling

Complexity