Skip to main content

Leetcode 18: 4Sum

 

1. Problem Statement (Simple Explanation):


You are given:

  • An integer array nums of length n

  • An integer target

You must find all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n

  • a, b, c, d are all distinct indices

  • nums[a] + nums[b] + nums[c] + nums[d] == target

Return:

  • A list of unique quadruplets (order in output doesn’t matter).

  • No duplicate quadruplets (same four values in possibly different order) should appear in the result.


2. 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]]

Valid quadruplets that sum to 0:

  • -2 + -1 + 1 + 2 = 0

  • -2 + 0 + 0 + 2 = 0

  • -1 + 0 + 0 + 1 = 0

After removing duplicates and sorting elements within each quadruplet, we get the three unique quadruplets above.


Example 2:

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

Output: [[2,2,2,2]]

Only one quadruplet exists: 2 + 2 + 2 + 2 = 8.


Constraints:


  • 1<=nums.length<=2001

  • -109 <= nums[i] <= 109

  • -109 <= target <= 109


3. Approach 1 – Brute Force (O(n⁴), Not Practical):


Conceptually:


  • Use 4 nested loops to try all combinations (a, b, c, d).

  • Check if their sum equals target.

  • Use a set to avoid duplicates.

This is:

  • Time: O(n4) → too slow for n up to 200.

  • Space: high if using a set of quadruplets.

So we need a better approach.


4. Approach 2 – Sort + Two Pointers + Pruning (O(n³), Recommended):


This is a generalization of the 3Sum two-pointer pattern.


High-Level Idea:


  1. Sort the array nums.

  2. Fix the first two indices i and j using two nested loops.

  3. For each pair (i, j):

    • We reduce the problem to 2Sum with target:

newTarget = target - nums[i] - nums[j]

  • Then perform a standard two-pointer 2Sum on the subarray from j+1 to n-1 to find pairs (left, right) whose sum equals newTarget.

  1. Skip duplicates for i, j, left, and right so we don’t add the same quadruplet multiple times.

  2. Optionally apply pruning using bounds (min/max possible sums) to break loops early, but for n <= 200, the straightforward O(n3) with duplicate skipping is acceptable.


Detailed Algorithm:


  1. Sort nums.

  2. Initialize result as an empty list.

  3. Let n = len(nums).

  4. For i from 0 to n - 4:

    • If i > 0 and nums[i] == nums[i-1], skip (to avoid duplicate first element).

    • For j from i + 1 to n - 3:

      • If j > i + 1 and nums[j] == nums[j-1], skip (to avoid duplicate second element).

      • Set:

        • left = j + 1

        • right = n - 1

        • twoSumTarget = target - nums[i] - nums[j]

      • While left < right:

        • twoSum = nums[left] + nums[right]

        • if twoSum == twoSumTarget:

          • Add quadruplet [nums[i], nums[j], nums[left], nums[right]] to result.

          • Move left forward while nums[left] == nums[left+1] to skip duplicates.

          • Move right backward while nums[right] == nums[right-1] to skip duplicates.

          • Then left++, right--.

        • else if twoSum < twoSumTarget:

          • left++ (we need a bigger sum).

        • else:

          • right-- (we need a smaller sum).

  5. Return result.


Pseudo-code:



Complexity:


Let n = len(nums)

  • Sorting: O(n*logn)

  • Outer loops: i and j each up to O(n)

  • Inner two-pointer per (i, j): O(n)

Total:

  • Time: O(n3)

  • Space: O(1) extra (ignoring output, sort in-place)

For n <= 200, O(n3) is acceptable.


5. Java code:



Note: used long for intermediate sums to avoid overflow when nums/target are near 109.


6. C code:



7. C++ code:



8. Python code:



9. JavaScript code:




Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more