Array Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the array exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and common pitfalls. Try the problems first — then check your work here.

Q1. Reverse an array in place

Idea: Use two pointers — one at each end — and swap, moving them toward the middle. This touches each element once and uses no extra array.

Complexity: O(n) time, O(1) extra space.

void reverse(std::vector<int>& a) {
    int i = 0, j = (int)a.size() - 1;
    while (i < j) std::swap(a[i++], a[j--]);
}

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

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

def reverse(a):
    i, j = 0, len(a) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

Pitfall: Looping all the way to the end (instead of the middle) reverses twice and returns the original array. Stop when i >= j.

Q2. Find the maximum element

Idea: Track a running maximum in one pass. Decide an empty-array policy up front — here we treat it as an error / return a sentinel.

Complexity: O(n) time, O(1) space.

int maxElement(const std::vector<int>& a) {
    int best = a[0]; // assume non-empty (validate before calling)
    for (int x : a) best = std::max(best, x);
    return best;
}

int maxElement(int[] a) {
    int best = a[0]; // assume non-empty (validate before calling)
    for (int x : a) best = Math.max(best, x);
    return best;
}

function maxElement(a) {
  let best = a[0]; // assume non-empty
  for (const x of a) best = Math.max(best, x);
  return best;
}

def max_element(a):
    best = a[0]  # assume non-empty
    for x in a:
        best = max(best, x)
    return best

Pitfall: Initializing best = 0 breaks on all-negative arrays. Initialize from the first element instead.

Q3. Sum of all elements

Idea: A single accumulation pass. Use a 64-bit accumulator if values can be large to avoid overflow.

Complexity: O(n) time, O(1) space.

long long sum(const std::vector<int>& a) {
    long long total = 0;
    for (int x : a) total += x;
    return total;
}

long sum(int[] a) {
    long total = 0;
    for (int x : a) total += x;
    return total;
}

function sum(a) {
  return a.reduce((t, x) => t + x, 0);
}

def sum_all(a):
    return sum(a)

Q4. Two Sum

Idea: The brute force checks every pair — O(n²). Instead, walk once with a hash map of value → index. For each x, check whether target - x was already seen. This trades O(n) memory for O(n) time.

Complexity: O(n) time, O(n) space.

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        if (seen.count(need)) return {seen[need], i};
        seen[nums[i]] = i;
    }
    return {};
}

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) return new int[]{seen.get(need), i};
        seen.put(nums[i], i);
    }
    return new int[]{};
}

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return [];
}

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

Pitfall: Storing the value before checking lets a single element pair with itself. Always check target - x first, then insert x.

Q5. Move zeros to the end

Idea: Keep a write pointer for the next non-zero slot. Scan once, copying non-zeros forward; fill the rest with zeros. This preserves order in O(n).

Complexity: O(n) time, O(1) space.

void moveZeros(std::vector<int>& a) {
    int write = 0;
    for (int x : a) if (x != 0) a[write++] = x;
    while (write < (int)a.size()) a[write++] = 0;
}

void moveZeros(int[] a) {
    int write = 0;
    for (int x : a) if (x != 0) a[write++] = x;
    while (write < a.length) a[write++] = 0;
}

function moveZeros(a) {
  let write = 0;
  for (const x of a) if (x !== 0) a[write++] = x;
  while (write < a.length) a[write++] = 0;
}

def move_zeros(a):
    write = 0
    for x in a:
        if x != 0:
            a[write] = x
            write += 1
    for i in range(write, len(a)):
        a[i] = 0

Q6. Maximum subarray sum (Kadane’s algorithm)

Idea: At each position decide: extend the current subarray, or start fresh from here. Track the best sum seen. The insight — a negative running sum can only hurt what follows, so drop it.

Complexity: O(n) time, O(1) space.

int maxSubArray(const std::vector<int>& a) {
    int best = a[0], cur = a[0];
    for (int i = 1; i < (int)a.size(); i++) {
        cur = std::max(a[i], cur + a[i]);
        best = std::max(best, cur);
    }
    return best;
}

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]);
        best = Math.max(best, cur);
    }
    return best;
}

function maxSubArray(a) {
  let best = a[0], cur = a[0];
  for (let i = 1; i < a.length; i++) {
    cur = Math.max(a[i], cur + a[i]);
    best = Math.max(best, cur);
  }
  return best;
}

def max_sub_array(a):
    best = cur = a[0]
    for x in a[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

Pitfall: Initializing best = 0 fails on all-negative arrays (the answer should be the largest single element). Seed both best and cur from a[0].

That’s the full answer sheet. Back to the array exercises or continue to linked lists.