Array Problems — Rotation, Subarrays, Intervals, In-Place Tricks — Interview Questions

How to use this lesson

For each problem, the answer gives the pattern, the key insight, the complexity, and a compact Java solution. In the interview:

1. clarify the constraints (negatives? duplicates? can the input be modified?);
2. state the brute force and its complexity;
3. give the optimal idea;
4. code it;
5. test it with edge cases (empty input, a single element, all negatives, duplicates).

Where a full practice page exists, follow the link.

Learn it in depth → Prefix Sums

Q1. Rotate an array by K steps (in place, O(1) space).

Short answer: Use the reversal trick. For a right rotation by k: k %= n; reverse the whole array, then reverse the first k elements, then reverse the rest. O(n) time, O(1) space.

void rotate(int[] a, int k) {
    int n = a.length; k %= n;
    reverse(a, 0, n - 1); reverse(a, 0, k - 1); reverse(a, k, n - 1);
}
void reverse(int[] a, int i, int j) { while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; } }

Common trap: forgetting k %= n (k can exceed n), or n == 0.

Q2. Find a subarray with a given sum (positive and negative numbers).

Short answer: A sliding window only works for non-negative numbers. With negatives, use prefix sums with a HashMap: keep a running sum s; if s - target has been seen at index i, the subarray (i+1 .. j) sums to the target. Seed the map with 0 → -1. O(n) time, O(n) space. For counting all such subarrays, store frequencies instead of indices (Subarray Sum Equals K).

int[] subarraySum(int[] a, int target) {
    Map<Long, Integer> firstIndex = new HashMap<>(Map.of(0L, -1));
    long s = 0;
    for (int j = 0; j < a.length; j++) {
        s += a[j];
        Integer i = firstIndex.get(s - target);
        if (i != null) return new int[]{i + 1, j};
        firstIndex.putIfAbsent(s, j);
    }
    return new int[0];
}

Q3. Maximum product subarray.

Short answer: Track both the maximum and the minimum product ending at each index, because a negative number turns the minimum into the maximum. At each element, swap max and min if it's negative. O(n), O(1).

int maxProduct(int[] a) {
    int max = a[0], min = a[0], best = a[0];
    for (int i = 1; i < a.length; i++) {
        if (a[i] < 0) { int t = max; max = min; min = t; }
        max = Math.max(a[i], max * a[i]);
        min = Math.min(a[i], min * a[i]);
        best = Math.max(best, max);
    }
    return best;
}

Q4. Trapping rain water (two approaches).

Short answer: The water at i is min(maxLeft[i], maxRight[i]) - h[i].

• Approach 1, prefix and suffix max arrays: O(n) time, O(n) space.
• Approach 2, two pointers: move the side with the smaller maximum, because that side's water level is bounded by its own maximum. O(n) time, O(1) space.

int trap(int[] h) {                          // two pointers
    int l = 0, r = h.length - 1, lmax = 0, rmax = 0, water = 0;
    while (l < r) {
        if (h[l] < h[r]) { lmax = Math.max(lmax, h[l]); water += lmax - h[l++]; }
        else             { rmax = Math.max(rmax, h[r]); water += rmax - h[r--]; }
    }
    return water;
}

A third option is a monotonic stack, which computes the water layer by layer (also O(n)).

Q5. Find the missing and the repeating number (values 1..n).

Short answer:

• Maths: with S = sum - n(n+1)/2 = rep - miss and P = sumSquares - n(n+1)(2n+1)/6 = rep² - miss², we get rep + miss = P / S. Use long to avoid overflow.
• Or XOR partitioning.
• Or index marking (negate a[|x|-1]; an already-negative slot reveals the repeat).

All are O(n) time, O(1) space.

int[] missingAndRepeating(int[] a) {
    long n = a.length, s = 0, sq = 0;
    for (int x : a) { s += x; sq += (long) x * x; }
    long diff = s - n * (n + 1) / 2;                       // rep - miss
    long sumSq = sq - n * (n + 1) * (2 * n + 1) / 6;       // rep^2 - miss^2
    long sum = sumSq / diff;                               // rep + miss
    long rep = (diff + sum) / 2;
    return new int[]{(int) rep, (int) (rep - diff)};
}

Q6. Kadane's algorithm, returning the indices.

Short answer: Extend the current subarray while its running sum is positive; otherwise restart at i (and record the start). When cur > best, save start and i. O(n), O(1). It handles all-negative arrays when you initialise with the first element. (Maximum Subarray)

int[] kadane(int[] a) {
    int best = a[0], cur = a[0], start = 0, bs = 0, be = 0;
    for (int i = 1; i < a.length; i++) {
        if (cur < 0) { cur = a[i]; start = i; } else cur += a[i];
        if (cur > best) { best = cur; bs = start; be = i; }
    }
    return new int[]{best, bs, be};
}

Q7. Product of an array except self.

Short answer: No division. Make a prefix-product pass into the output array, then multiply by a running suffix product from the right. O(n) time, O(1) extra (the output array doesn't count). (Practice)

int[] productExceptSelf(int[] a) {
    int n = a.length; int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) res[i] = res[i - 1] * a[i - 1];
    for (int i = n - 1, suffix = 1; i >= 0; i--) { res[i] *= suffix; suffix *= a[i]; }
    return res;
}

Q8. Merge overlapping intervals. Insert an interval into sorted intervals.

Short answer:

• Merge: sort by start; extend the last merged interval while next.start <= last.end. O(n log n). (Merge Intervals)
• Insert (the input is already sorted and non-overlapping): add all the intervals ending before the new one; merge all those overlapping it (the minimum start, the maximum end); add the rest. O(n).

int[][] merge(int[][] iv) {
    Arrays.sort(iv, Comparator.comparingInt(x -> x[0]));
    List<int[]> out = new ArrayList<>();
    for (int[] cur : iv) {
        if (out.isEmpty() || out.get(out.size() - 1)[1] < cur[0]) out.add(cur);
        else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], cur[1]);
    }
    return out.toArray(int[][]::new);
}
int[][] insert(int[][] iv, int[] nw) {
    List<int[]> out = new ArrayList<>(); int i = 0, n = iv.length;
    while (i < n && iv[i][1] < nw[0]) out.add(iv[i++]);
    while (i < n && iv[i][0] <= nw[1]) { nw[0] = Math.min(nw[0], iv[i][0]); nw[1] = Math.max(nw[1], iv[i][1]); i++; }
    out.add(nw);
    while (i < n) out.add(iv[i++]);
    return out.toArray(int[][]::new);
}

Learn it in depth → Merge Intervals Pattern

Q9. Next permutation.

Short answer:

1. From the right, find the first i with a[i] < a[i+1] (the pivot).
2. If it exists, swap it with the rightmost element greater than it.
3. Reverse the suffix after i. If there's no pivot, reverse the whole array (it's the last permutation, so wrap to the first).

O(n), O(1).

void nextPermutation(int[] a) {
    int i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i >= 0) { int j = a.length - 1; while (a[j] <= a[i]) j--; swap(a, i, j); }
    reverse(a, i + 1, a.length - 1);
}

Q10. The Dutch national flag problem (sort 0s, 1s and 2s).

Short answer: Three pointers: low, mid and high.

• a[mid] == 0: swap it with low, and advance both.
• == 1: advance mid.
• == 2: swap it with high, and decrement high (don't advance mid: the swapped-in value still needs checking).

One pass, O(n), O(1).

void sortColors(int[] a) {
    int lo = 0, mid = 0, hi = a.length - 1;
    while (mid <= hi) {
        if (a[mid] == 0) swap(a, lo++, mid++);
        else if (a[mid] == 1) mid++;
        else swap(a, mid, hi--);
    }
}

Q11. Majority element II (elements appearing more than n/3 times).

Short answer: There can be at most 2 such elements. Use the extended Boyer-Moore voting algorithm, with two candidates and two counters. Then verify the counts in a second pass (the candidates aren't guaranteed). O(n), O(1).

List<Integer> majorityElement(int[] a) {
    int c1 = 0, c2 = 1, n1 = 0, n2 = 0;
    for (int x : a) {
        if (x == c1) n1++; else if (x == c2) n2++;
        else if (n1 == 0) { c1 = x; n1 = 1; } else if (n2 == 0) { c2 = x; n2 = 1; }
        else { n1--; n2--; }
    }
    List<Integer> res = new ArrayList<>();
    for (int c : new int[]{c1, c2}) {
        long cnt = Arrays.stream(a).filter(x -> x == c).count();
        if (cnt > a.length / 3 && !res.contains(c)) res.add(c);
    }
    return res;
}

Q12. Longest consecutive sequence in O(n).

Short answer: Put everything in a HashSet. Start counting only from the numbers that are sequence starts (x-1 isn't in the set), and walk forward. Each number is visited at most twice, so it's O(n).

int longestConsecutive(int[] a) {
    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 y = x; while (set.contains(y + 1)) y++;
        best = Math.max(best, y - x + 1);
    }
    return best;
}

Q13. The gas station (circular tour) problem.

Short answer:

• If sum(gas) < sum(cost), there's no solution.
• Otherwise, scan once with a running tank; when the tank goes negative at i, no station from the current start to i can be the start, so restart at i+1 with an empty tank.

O(n), O(1). (Gas Station)

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int d = gas[i] - cost[i]; total += d; tank += d;
        if (tank < 0) { start = i + 1; tank = 0; }
    }
    return total < 0 ? -1 : start;
}

Q14. The candy distribution problem.

Short answer: Every child gets at least 1 candy, and a child with a higher rating than a neighbour gets more than that neighbour. Two passes:

• left to right: c[i] = c[i-1] + 1 if its rating is higher than the left neighbour;
• right to left: c[i] = max(c[i], c[i+1] + 1) if it's higher than the right neighbour.

Sum them. O(n) time, O(n) space. (An O(1)-space slope-counting version exists.)

int candy(int[] r) {
    int n = r.length; int[] c = new int[n]; Arrays.fill(c, 1);
    for (int i = 1; i < n; i++) if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--) if (r[i] > r[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
    return Arrays.stream(c).sum();
}

Q15. Find the duplicate number using Floyd's cycle detection.

Short answer: With n+1 values in 1..n, treat i → a[i] as a linked list; the duplicate is the entrance of the cycle. Use the tortoise and hare to meet inside the cycle, then reset one pointer to the start, and move both one step at a time until they meet. O(n) time, O(1) space, and the array isn't modified. (Practice)

int findDuplicate(int[] a) {
    int slow = a[0], fast = a[0];
    do { slow = a[slow]; fast = a[a[fast]]; } while (slow != fast);
    slow = a[0];
    while (slow != fast) { slow = a[slow]; fast = a[fast]; }
    return slow;
}

Learn it in depth → Fast & Slow Pointers

Q16. First missing positive.

Short answer: The answer is in 1..n+1. Use cyclic sort in place: put each value v in 1..n at index v-1 (swap it until it's in position, or it's a duplicate). Then the first index i with a[i] != i+1 gives i+1. O(n) time, O(1) space. (Practice)

int firstMissingPositive(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++)
        while (a[i] > 0 && a[i] <= n && a[a[i] - 1] != a[i]) swap(a, i, a[i] - 1);
    for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
    return n + 1;
}

Learn it in depth → Cyclic Sort

Follow-up questions this topic invites — and their answers

Q: Why doesn't the sliding window work for subarray sums with negative numbers? A: The window logic assumes that growing the window increases the sum and shrinking it decreases it. With negatives that's false, so you can't decide which side to move. Prefix sums with a hash map handle any values.

Q: How do you avoid integer overflow in these problems? A: Use long for sums and products of sums, Math.addExact/multiplyExact when you need detection, and lo + (hi - lo) / 2 for midpoints.

Q: When is modifying the input array acceptable? A: Ask the interviewer. In-place tricks (cyclic sort, index marking) give O(1) space, but they mutate the caller's data; Floyd's method for the duplicate avoids that.

Q: What's the general pattern behind the gas station and Kadane solutions? A: A greedy reset: when the running quantity becomes useless (negative), no prefix ending there can help, so restart from the next index. That's why a single pass is enough.