Introduction

In this blog post, we will explore how to solve the LeetCode problem "18" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given an array nums of n integers, return an array of all the 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. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order. 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]] Constraints: 1 <= nums.length <= 200 -109 <= nums[i] <= 109 -109 <= target <= 109

Explanation

Here's a breakdown of the approach and the Python code:

• High-Level Approach:

  • Sorting: Sort the input array nums. This enables efficient skipping of duplicate quadruplets and allows for the two-pointer technique.
  • Nested Loops and Two Pointers: Use nested loops to select the first two numbers of the quadruplet. Then, use the two-pointer technique on the remaining portion of the sorted array to find the other two numbers that satisfy the target sum condition.
  • Duplicate Handling: Implement checks to skip duplicate numbers at each level of the nested loops and within the two-pointer approach, ensuring that only unique quadruplets are added to the result.

• Complexity:

  • Runtime: O(n^3), Storage: O(1) excluding the output array (which can be O(n) in the worst case)

Code

    def fourSum(nums, target):
    """
    Finds all unique quadruplets in nums that sum to target.

    Args:
        nums: A list of integers.
        target: The target sum.

    Returns:
        A list of lists, where each inner list is a unique quadruplet.
    """

    n = len(nums)
    if n < 4:
        return []

    nums.sort()
    result = []

    for i in range(n - 3):
        # Skip duplicate numbers for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        for j in range(i + 1, n - 2):
            # Skip duplicate numbers for the second element
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            left = j + 1
            right = n - 1

            while left < right:
                current_sum = nums[i] + nums[j] + nums[left] + nums[right]

                if current_sum == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])

                    # Skip duplicate numbers for the third element
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    # Skip duplicate numbers for the fourth element
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1
                elif current_sum < target:
                    left += 1
                else:
                    right -= 1

    return result