Array and two-pointer interview questions, with answers

The questions, with answers

1. 1Which operations on an array are O(1), and which need a scan?

   Reading or writing by index is O(1): the address is the base plus index times element size. Reading the length is O(1). Everything that depends on the values needs a scan: finding the maximum or minimum, searching an unsorted array, counting occurrences — all O(n), because any element could be the one you want. Inserting or deleting in the middle is O(n) too, since the elements after the position have to shift. Sorted arrays change the picture for search only — binary search makes it O(log n) — but not for insertion. Interviewers ask this to see whether you know which cost you are paying; "find the max of an unsorted array in O(1)" is a trick with no answer.

2. 2How do you reverse an array in place?

   Two pointers, one at each end: swap the elements they point to, move the left pointer right and the right pointer left, and stop when they meet or cross. Each element is touched once, so it is O(n) time, and no second array is allocated, so O(1) extra space — the phrase "in place" is what the question is testing. The loop condition is left < right; with an odd length the middle element stays put, and with an even length the last swap is the central pair. The same shape reverses a substring, rotates an array (reverse the whole thing, then reverse each part), and checks a palindrome.

   Copy

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

3. 3How do you find a pair with a given sum in a sorted array?

   Point one index at the start and one at the end, and look at their sum. If it equals the target you are done; if it is too small, only moving the left pointer right can increase it, so do that; if it is too large, move the right pointer left. Each step discards one element from consideration, so it finishes in O(n) time with O(1) space — against O(n²) for checking every pair, or O(n) time and O(n) space for the hash-set approach that also works on unsorted input. The reasoning that a step never skips a valid pair is what the interviewer wants to hear: when the sum is too small, no pair using the current right element can work, because every other partner is even smaller.

   Copy

   boolean pairSum(int[] a, int target) {   // a is sorted ascending
       int i = 0, j = a.length - 1;
       while (i < j) {
           int s = a[i] + a[j];
           if (s == target) return true;
           if (s < target) i++; else j--;
       }
       return false;
   }

4. 4How do you remove duplicates from a sorted array in place?

   The slow-fast pointer pattern. A write pointer marks the end of the deduplicated prefix; a read pointer scans the array. Whenever the read pointer sees a value different from the last written one, copy it to the write position and advance the write pointer. When the scan ends, the first write-pointer elements are the unique values in order, and the function returns that count — the rest of the array is garbage the caller ignores. O(n) time, O(1) space, and it only works because the array is sorted, so equal values are adjacent. The same read/write shape moves all zeros to the end, removes every occurrence of a value, and compacts an array around any predicate.

   Copy

   int dedupe(int[] a) {          // sorted; returns the new length
       if (a.length == 0) return 0;
       int w = 1;
       for (int r = 1; r < a.length; r++)
           if (a[r] != a[w - 1]) a[w++] = a[r];
       return w;
   }

5. 5What is the sliding window technique, and when does it apply?

   A window is a contiguous range [left, right] that grows by moving right and shrinks by moving left, maintaining some running statistic so you never recompute it from scratch. Fixed-size windows answer "maximum sum of any k consecutive elements": add the entering element, subtract the leaving one, O(n) instead of O(n × k). Variable-size windows answer "longest substring without repeating characters" or "smallest subarray with sum at least S": extend right while the window is valid, shrink from the left when it is not. It applies when the answer is a contiguous range and validity is monotonic — if a window is invalid, growing it cannot make it valid. Negative numbers break that monotonicity for sum problems, which is the standard follow-up and the reason Kadane's algorithm exists.

6. 6How does Kadane's algorithm find the maximum subarray sum?

   Scan once, keeping the best sum of a subarray that ends at the current position: current = max(a[i], current + a[i]). If the running sum so far has gone negative, it can only drag a new subarray down, so you restart at a[i]; otherwise you extend. The answer is the maximum of current over the whole scan. O(n) time, O(1) space. Two details interviewers probe: initialise with the first element rather than 0, so an all-negative array returns its largest element rather than an empty sum; and if they want the subarray itself, record the start index whenever you restart and the end index whenever the best improves. For the array 3, -4, 5, -1, 2, -6, 4 the answer is 6, from 5, -1, 2: the running sum restarts at 5 after 3 - 4 dips below zero.

   Copy

   int maxSubarray(int[] a) {
       int best = a[0], cur = a[0];
       for (int i = 1; i < a.length; i++) {
           cur = Math.max(a[i], cur + a[i]);   // extend or restart
           best = Math.max(best, cur);
       }
       return best;
   }

7. 7How do you sort an array of 0s, 1s and 2s in one pass?

   The Dutch national flag algorithm, with three pointers: low marks the end of the 0s region, high marks the start of the 2s region, and mid scans between them. If a[mid] is 0, swap it with a[low] and advance both; if it is 2, swap it with a[high] and decrement high but do not advance mid, because the element that just arrived from the right is unexamined; if it is 1, just advance mid. When mid passes high, the array is sorted, in O(n) time and O(1) space with a single pass. Counting the three values and rewriting the array is also O(n) but needs two passes and does not generalise; the three-pointer partition is the same idea quicksort uses and is what the question is really about.

8. 8How do you find the majority element in O(n) time and O(1) space?

   Boyer-Moore majority vote. Keep a candidate and a count. For each element: if the count is 0, adopt the element as the candidate; then add 1 to the count if the element equals the candidate and subtract 1 otherwise. Because a true majority appears more than n/2 times, every time it is cancelled by a different element it still has votes to spare, so it is the candidate at the end. The catch: the algorithm returns a candidate even when no majority exists, so unless the problem guarantees one, do a second pass to count the candidate's occurrences and confirm they exceed n/2. A hash map of counts also works in O(n) time but costs O(n) space, and sorting and taking the middle element is O(n log n) — both are acceptable first answers, and Boyer-Moore is the follow-up.