FastPrep4Sum
Problem · Array

4Sum

Learn this problem
● MediumAmazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

Given an integer array nums and an integer target, return every unique quadruplet of values [a, b, c, d] whose elements come from four distinct indices and satisfy a + b + c + d = target.

Sort the values inside each quadruplet in nondecreasing order. Return the unique quadruplets in lexicographic order.

Function

fourSum(nums: int[], target: int) → int[][]

Examples

Example 1

nums = [1,0,-1,0,-2,2]target = 0return = [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

These are the three distinct sorted quadruplets whose sum is 0.

Example 2

nums = [2,2,2,2,2]target = 8return = [[2,2,2,2]]

Many index choices produce the same values, so the quadruplet appears once.

Example 3

nums = [1,2,3]target = 6return = []

Fewer than four elements cannot form a quadruplet.

Constraints

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

More Amazon problems

drafts saved locally
public int[][] fourSum(int[] nums, int target) {
  // write your code here
}
nums[1,0,-1,0,-2,2]
target0
expected[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
checking account