LeetCode #18 - 4 Sum

Hello happy people πŸ‘‹! It’s time for another LeetCode problem.

Problem Statement

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Notice that the solution set must not contain duplicate quadruplets.

Constraints:

  • 0 ≀ nums.length ≀ 200
  • -109 ≀ nums[i] ≀ 109
  • -109 ≀ target ≀ 109

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 = [], target = 0
Output: []

Analysis

We have seen problems like this before β€” Two Sum, 3 Sum and 3 Sum Closest.

A simple way to solve 4 Sum problem is to reduce it to 3 Sum problem which can further be reduced to Two Sum problem. Therefore, here our aim is to find a combination of four numbers and all such combinations are unique.

Approach

The steps can be as follows β€”

  1. Sort the array in time O(n * log n).
  2. Now for each element i and j, do the following steps β€”
  3. Set two pointers left β€” k = j + 1 and right β€” l = n - 1.
  4. Check if nums[i] + nums[j] + nums[k] + nums[l] == target and add it to the result, if true/
  5. If nums[i] + nums[j] + nums[k] + nums[l] < target, then we are too left, and we need to move right so increment left pointer i.e. k++.
  6. If nums[i] + nums[j] + nums[k] + nums[l] > target, then we are too right, and we need to decrement the right pointer i.e., l--.

Time Complexity

We are scanning the entire array keeping one element fixed and then doing it for another element fixed. We are doing this for every element in the array. Thus, we are scanning each element of array n number of times. And we are doing this for n times, hence the worst case time complexity will be O(n3 + n * log n) which comes down to O(n3).

Space Complexity

We are not using any data structure for the intermediate computations, hence the space complexity is O(1).

Code

Java

public class FourSum {

    private static List<List<Integer>> fourSum(int[] nums, int target) {
        // Resultant list
        List<List<Integer>> quadruplets = new ArrayList<>();
        // Base condition
        if (nums == null || nums.length < 4) {
            return quadruplets;
        }
        // Sort the array
        Arrays.sort(nums);
        // Length of the array
        int n = nums.length;
        // Loop for each element in the array
        for (int i = 0; i < n - 3; i++) {
            // Check for skipping duplicates
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // Reducing problem to 3Sum problem
            for (int j = i + 1; j < n - 2; j++) {
                // Check for skipping duplicates
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // Left and right pointers
                int k = j + 1;
                int l = n - 1;
                // Reducing to two sum problem
                while (k < l) {
                    int currentSum = nums[i] + nums[j] + nums[k] + nums[l];
                    if (currentSum < target) {
                        k++;
                    } else if (currentSum > target) {
                        l--;
                    } else {
                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                        k++;
                        l--;
                        // Check for skipping duplicates
                        while (k < l && nums[k] == nums[k - 1]) {
                            k++;
                        }
                        while (k < l && nums[l] == nums[l + 1]) {
                            l--;
                        }
                    }
                }
            }
        }
        return quadruplets;
    }
}

Python

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    # Resultant list
    quadruplets = list()
    # Base condition
    if nums is None or len(nums) < 4:
        return quadruplets
    # Sort the array
    nums.sort()
    # Length of the array
    n = len(nums)
    # Loop for each element of the array
    for i in range(0, n - 3):
        # Check for skipping duplicates
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # Reducing to three sum problem
        for j in range(i + 1, n - 2):
            # Check for skipping duplicates
            if j != i + 1 and nums[j] == nums[j - 1]:
                continue
            # Left and right pointers
            k = j + 1
            l = n - 1
            # Reducing to two sum problem
            while k < l:
                current_sum = nums[i] + nums[j] + nums[k] + nums[l]
                if current_sum < target:
                    k += 1
                elif current_sum > target:
                    l -= 1
                else:
                    quadruplets.append([nums[i], nums[j], nums[k], nums[l]])
                    k += 1
                    l -= 1
                    while k < l and nums[k] == nums[k - 1]:
                        k += 1
                    while k < l and nums[l] == nums[l + 1]:
                        l -= 1
    return quadruplets

JavaScript

var fourSum = function (nums, target) {
    // Resultant list
    const quadruplets = [];
    // Base condition
    if (nums == undefined || nums.length < 4) {
        return quadruplets;
    }
    // Sort the array
    nums.sort((a, b) => a - b);
    // Length of the array
    const n = nums.length;
    // Loop for each element of the array
    for (let i = 0; i < n - 3; i++) {
        // Check for skipping duplicates
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // Reducing to three sum problem
        for (let j = i + 1; j < n - 2; j++) {
            // Check for skipping duplicates
            if (j != i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            // Left and right pointers
            let k = j + 1;
            let l = n - 1;
            // Reducing to two sum problem
            while (k < l) {
                const currentSum = nums[i] + nums[j] + nums[k] + nums[l];
                if (currentSum < target) {
                    k++;
                } else if (currentSum > target) {
                    l--;
                } else {
                    quadruplets.push([nums[i], nums[j], nums[k], nums[l]]);
                    k++;
                    l--;
                    // Check for skipping duplicates
                    while (k < l && nums[k] == nums[k - 1]) {
                        k++;
                    }
                    while (k < l && nums[l] == nums[l + 1]) {
                        l--;
                    }
                }
            }
        }
    }
    return quadruplets;
};

Kotlin

fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
    // Resultant list
    val quadruplets: MutableList<List<Int>> = ArrayList()
    // Base condition
    if (nums.size < 4) {
        return quadruplets
    }
    // Sort the array
    Arrays.sort(nums)
    // Length of the array
    val n = nums.size
    // Loop for each element in the array
    for (i in 0 until n - 3) {
        // Check for skipping duplicates
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue
        }
        // Reducing problem to 3Sum problem
        for (j in i + 1 until n - 2) {
            // Check for skipping duplicates
            if (j != i + 1 && nums[j] == nums[j - 1]) {
                continue
            }
            // Left and right pointers
            var k = j + 1
            var l = n - 1
            // Reducing to two sum problem
            while (k < l) {
                val currentSum = nums[i] + nums[j] + nums[k] + nums[l]
                when {
                    currentSum < target -> {
                        k++
                    }
                    currentSum > target -> {
                        l--
                    }
                    else -> {
                        quadruplets.add(listOf(nums[i], nums[j], nums[k], nums[l]))
                        k++
                        l--
                        // Check for skipping duplicates
                        while (k < l && nums[k] == nums[k - 1]) {
                            k++
                        }
                        while (k < l && nums[l] == nums[l + 1]) {
                            l--
                        }
                    }
                }
            }
        }
    }
    return quadruplets
}

Complete Code

Conclusion

Congratulations πŸ‘! We have solved one more problem from LeetCode and it was extension of the few we solved πŸ˜ƒ.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork πŸ”ͺ and star ⭐ it.

Till next time… Happy coding πŸ˜„ and Namaste πŸ™!


Created and maintained by@Anirudh Sharma
I love to learn and share. Hence, this site has no ads, no affiliation links, or any BS. If you like what you see, give me a thumbs up.

GitHub iconMedium iconTwitter iconFacebook iconLinkedIn iconStackoverflow icon