Katkat
Back

Find all quadruplets summing to target

SnapchatMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize nested loops using a two-pointer approach to achieve a time complexity better than brute force when searching for subsets of a fixed size that sum to a target value.

Find All Quadruplets

Given an integer array nums and an integer target, return an array of all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct indices.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order. The solution must ensure that each quadruplet in the output is unique (i.e., the set of values is not repeated).

Function Signature

def fourSum(nums: list[int], target: int) -> list[list[int]]:

Constraints

  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

Examples

Example 1: Input: nums = [1, 0, -1, 0, -2, 2], target = 0 Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Example 2: Input: nums = [2, 2, 2, 2, 2], target = 8 Output: [[2, 2, 2, 2]]

Edge Cases

  • Array length less than 4 (should return an empty list).
  • Input containing all duplicates.
  • Large values that may exceed standard integer limits (though Python handles this automatically).

Hints

Hint 1

Start by sorting the array to make it easier to handle duplicates and utilize the two-pointer technique.

Hint 2

Use two nested loops to fix the first two numbers, then treat the remaining two as a classic 'Two Sum' problem on a sorted array.

Hint 3

When iterating, skip duplicate values by checking if the current element is equal to the previous element to avoid redundant quadruplets in your results.

Follow-up questions

  • How would you generalize this solution to find k-sized subsets that sum to a target?
  • What is the time complexity of your current solution, and can it be improved using a hash map for the last two elements?
  • If the array was extremely large and couldn't fit into memory, how would you approach this problem?