3Sum - Leetcode Solution

Problem Link

💡Optimal Solution: HashMap

Convert to Negative Values: Since heapq provides a min heap (where the smallest element is at the root), we negate all elements in nums by iterating through the array and setting nums[i] = -nums[i]. This effectively simulates a max heap, where the largest original value corresponds to the smallest (most negative) value in the heap.
Heapify the Array: We call heapq.heapify(nums) to rearrange the array into a min heap based on the negated values. This operation ensures that the smallest negated value (corresponding to the largest original value) is at the root.
Pop k-1 Elements: To find the kth largest element, we remove the smallest negated value (largest original value) from the heap k-1 times using heapq.heappop(nums). Each pop operation removes the root and re-heapifies the remaining elements, bringing the next smallest negated value to the root.
Extract the Kth Largest: After k-1 pops, the root of the heap is the kth smallest negated value (kth largest original value). We pop this element with heapq.heappop(nums) and return its negation (i.e., -heapq.heappop(nums)) to obtain the original positive value.

Code Solution (HashMap)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        h = {}
        n = len(nums)
        s = set()

        for i, num in enumerate(nums):
            h[num] = i

        for i in range(n):
            for j in range(i + 1, n):
                desired = -nums[i] - nums[j]
                if desired in h and h[desired] != i and h[desired] != j:
                    s.add(tuple(sorted([nums[i], nums[j], desired])))

        return s

# Time Complexity: O(n^2)
# Space Complexity: O(n)

#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int, int> indexMap;
        set<vector<int>> result;
        int n = nums.size();

        // Build the index map
        for (int i = 0; i < n; ++i) {
            indexMap[nums[i]] = i;
        }

        // Iterate over each pair
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int desired = -nums[i] - nums[j];
                if (indexMap.find(desired) != indexMap.end() &&
                    indexMap[desired] != i && indexMap[desired] != j) {
                    vector<int> triplet = {nums[i], nums[j], desired};
                    sort(triplet.begin(), triplet.end());
                    result.insert(triplet);
                }
            }
        }

        return vector<vector<int>>(result.begin(), result.end());
    }
};

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        Map<Integer, Integer> indexMap = new HashMap<>();
        int n = nums.length;

        // Build the index map
        for (int i = 0; i < n; i++) {
            indexMap.put(nums[i], i);
        }

        // Iterate over each pair
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int desired = -nums[i] - nums[j];
                if (indexMap.containsKey(desired) && indexMap.get(desired) != i && indexMap.get(desired) != j) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], desired);
                    Collections.sort(triplet);
                    result.add(triplet);
                }
            }
        }

        return new ArrayList<>(result);
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const indexMap = new Map();
    const result = new Set();
    const n = nums.length;

    // Build the index map
    for (let i = 0; i < n; i++) {
        indexMap.set(nums[i], i);
    }

    // Iterate over each pair
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const desired = -nums[i] - nums[j];
            if (indexMap.has(desired) && indexMap.get(desired) !== i && indexMap.get(desired) !== j) {
                const triplet = [nums[i], nums[j], desired].sort((a, b) => a - b);
                result.add(triplet.toString());
            }
        }
    }

    return Array.from(result, str => str.split(',').map(Number));
};

💡Optimal Solution: Two Pointers

Initialize Min Heap: We create an empty list min_heap to serve as a min heap, which will store at most k elements. The heap will maintain the smallest element at the root.
Process Each Element: We iterate through each number num in nums:
- If the heap has fewer than k elements, we push num onto the heap using heapq.heappush(min_heap, num). This builds the initial set of k candidates.
- If the heap already has k elements, we use heapq.heappushpop(min_heap, num). This operation pushes num onto the heap and immediately pops the smallest element, ensuring the heap maintains exactly k elements. If num is larger than the smallest element in the heap, it replaces it; otherwise, num is discarded.
Extract Result: After processing all elements, the heap contains the k largest elements, with the smallest of these (the kth largest) at the root. We return min_heap[0], the root of the heap.

Code Solution (Two Pointers)

[class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        answer = []
        for i in range(n):
            if nums[i] > 0:
                break
            elif i > 0 and nums[i] == nums[i-1]:
                continue
            lo, hi = i+1, n-1
            while lo < hi:
                summ = nums[i] + nums[lo] + nums[hi]
                if summ == 0:
                    answer.append([nums[i], nums[lo], nums[hi]])
                    lo, hi = lo+1, hi-1
                    while lo < hi and nums[lo] == nums[lo-1]:
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi+1]:
                        hi -= 1
                elif summ < 0:
                    lo += 1
                else:
                    hi -= 1
        
        return answer
        # Time: O(n^2)
        # Space: O(n) (Excluding the output)

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> answer;

        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int lo = i + 1, hi = n - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum == 0) {
                    answer.push_back({nums[i], nums[lo], nums[hi]});
                    lo++;
                    hi--;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                } else if (sum < 0) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }

        return answer;
    }
};

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int lo = i + 1, hi = n - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum == 0) {
                    answer.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    lo++;
                    hi--;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                } else if (sum < 0) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }

        return answer;
    }
}

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    let n = nums.length;
    let answer = [];

    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            break;
        }
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let lo = i + 1, hi = n - 1;
        while (lo < hi) {
            let sum = nums[i] + nums[lo] + nums[hi];
            if (sum === 0) {
                answer.push([nums[i], nums[lo], nums[hi]]);
                lo++;
                hi--;
                while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
                while (lo < hi && nums[hi] === nums[hi + 1]) hi--;
            } else if (sum < 0) {
                lo++;
            } else {
                hi--;
            }
        }
    }

    return answer;
};

Detailed Explanation

Understanding the Problem: Valid Palindrome

The “Valid Palindrome” problem asks us to determine whether a given string is a palindrome. A palindrome reads the same forward and backward. However, we must ignore case differences and non-alphanumeric characters (like spaces, punctuation, etc.).

For example:

"A man, a plan, a canal: Panama" → Output: true
"race a car" → Output: false

The goal is to clean the string and then check if the cleaned version is equal to its reverse.

Why This Problem Matters

This problem is a great test of string manipulation and two-pointer techniques. It also has practical applications in input validation, text normalization, and pattern recognition systems.

Optimal Approach: Two Pointers with Character Checks

Instead of cleaning the entire string upfront, we can use two pointers to scan from both ends and compare only valid characters. This approach is both time- and space-efficient, avoiding the need to create a new cleaned string.

Steps:

Initialize two pointers:
- left = 0 (start of string)
- right = s.length - 1 (end of string)
While left < right:
- If s[left] is not alphanumeric, move left forward.
- If s[right] is not alphanumeric, move right backward.
- Compare the lowercase of both characters:
  - If they don't match, return false.
  - If they match, continue inward: increment left, decrement right.
If the loop completes without mismatch, return true.

Example Walkthrough

Input: "A man, a plan, a canal: Panama"
Cleaned version: "amanaplanacanalpanama"
After two-pointer scan, all characters match → return true.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string. Each character is visited at most once.
Space Complexity: O(1), since we're not using extra memory beyond the two pointers.

Edge Cases to Consider

Empty string → considered a palindrome → return true
String with only non-alphanumeric characters → return true
Mixed case letters → should be treated as equal
Symbols, punctuation, and whitespace are ignored

Conclusion

The “Valid Palindrome” problem is an excellent example of how to handle real-world messy input efficiently. It reinforces essential techniques like input sanitization, case-insensitive comparison, and space-efficient scanning with two pointers. Mastering this approach is useful in a wide variety of scenarios, including data preprocessing and text validation tasks.

Get Personalized Support at AlgoMap Bootcamp 💡