Move Zeroes

Problem Description

Given an array, move all zeroes to the end while preserving the relative order of non-zero elements. No new array may be created.

Approach

This problem uses a technique similar to Remove Duplicates from Sorted Array — solve it with two pointers. Define a pointer p that only advances when the current element is non-zero.

public void moveZero(int[] nums) {
    int p = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[p] = nums[i];
            p++;
        }
    }

    while (p < nums.length) {
        nums[p] = 0;
        p++;
    }
}

The key insight is to split the work into two distinct steps: first move non-zero elements forward, then fill the remaining positions with zeroes. Time complexity: O(n). Space complexity: O(1).

Intersection of Two Arrays II

Problem Description

Given two arrays nums1 and nums2, return their intersection — including duplicates.

Approach

Solution 1

The first approach is to sort both arrays and use two pointers to find common elements.

public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);

    List<Integer> result = new ArrayList<>();
    int i = 0, j = 0;

    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] > nums2[j]) {
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            result.add(nums1[i]);
            i++;
            j++;
        }
    }

    return result.stream().mapToInt(Integer::intValue).toArray();
}

Time complexity is O(n log n + m log m) because of the two sorts. The two-pointer scan itself is O(n + m) since both pointers only move forward. Space complexity is O(min(n, m)) for the result list. Java’s Arrays.sort(int[]) uses Dual-Pivot Quicksort with O(log n) call stack depth, which is dominated by min(n, m) and can be ignored.

Solution 2

The second approach uses a HashMap to count occurrences of each element in nums1, then iterates through nums2 to collect matches.

public int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> countMap = new HashMap<>();

    for (int num : nums1) {
        countMap.merge(num, 1, Integer::sum);
    }

    List<Integer> result = new ArrayList<>();

    for (int num : nums2) {
        int count = countMap.getOrDefault(num, 0);
        if (count > 0) {
            result.add(num);
            countMap.put(num, count - 1);
        }
    }

    return result.stream().mapToInt(Integer::intValue).toArray();
}

3Sum

Problem Description

Find all unique triplets in the array that sum to zero.

Approach

Solution 1

The brute-force approach uses three nested loops. Whenever a valid triplet is found, sort it and add it to the result only if it isn’t already there.

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if ((nums[i] + nums[j] + nums[k]) == 0) {
                    List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k]);
                    temp.sort(Integer::compareTo);
                    if (!ret.contains(temp)) {
                        ret.add(temp);
                    }
                }
            }
        }
    }
    return ret;
}

Time complexity: O(n⁴) — the contains check on the list adds another O(n) factor. Space complexity: O(n).

Solution 2

A better approach uses sorting plus two pointers.

• Sort the array to shrink the search space.
• For each unique index i, run two pointers: j = i + 1 and k = nums.length - 1.
• If the sum exceeds 0, decrement k; if it falls below 0, increment j; if it equals 0, record the triplet and skip duplicate values for both pointers.

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> returns = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum > 0) k--;
            if (sum < 0) j++;
            if (sum == 0) {
                returns.add(Arrays.asList(nums[i], nums[j], nums[k]));
                j++;
                k--;
                while (j < nums.length - 1 && nums[j] == nums[j - 1]) j++;
                while (k > j && nums[k] == nums[k + 1]) k--;
            }
        }
    }
    return returns;
}