Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Problem Challenge 1: Quadruple Sum to Target

Problem Statement

Given an array of unsorted numbers and a target number, find all unique quadruplets in it, whose sum is equal to the target number.

Example 1:

Input: [4, 1, 2, -1, 1, -3], target=1
Output: [-3, -1, 1, 4], [-3, 1, 1, 2]
Explanation: Both the quadruplets add up to the target.

Example 2:

Input: [2, 0, -1, 1, -2, 2], target=2
Output: [-2, 0, 2, 2], [-1, 0, 1, 2]
Explanation: Both the quadruplets add up to the target.

Constraints:

  • 1 <= nums.length <= 200
  • -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

.....

.....

.....

Like the course? Get enrolled and start learning!
D

Deko

· 4 years ago

Please, add more visual explanations to these problems. A few of them have it but usually the most difficult ones are lacking it. I don't want to just memorize the solution, I want to actually understand how you got to that solution. I see many people on the discussion boards resorting to youtube videos to complement the explanations.

Show 1 reply
S

singhursefamily

· a year ago

The complexity analysis says the storage requirement for the quadruplets is O(N^3). Wouldn't it rather be O(N^4)?

The problem seems to be an example of the discrete math formula X choose Y which is X! / (Y! * (X-Y)!). How many ways are there to pick a subset of Y elements from a set of population X?

In this case, we have N choose 4, which is N! / (4! * (N-4)!), which would give an expression of degree 4 in terms of N.

L

Learner

· 5 years ago

For this line of code: int sum = arr[first] + arr[second] + arr[left] + arr[right];

What's the best way to handle overflow case?

For ex: [1000000000,1000000000,1000000000,1000000000] 0

Is typecasting to "long long" a good solution? long long diff = (long long)targetSum - arr[first] - arr[second] - arr[left] - arr[right];

The above typecasting helps but is there a better way to handle overflow case?

Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

I don't agree with official solution its way to complicated and not practice for interview session

class Solution:

  '''
    first sort the array 

    Then for each array element at i, j 

    add elements at i and j

    now we need to find the remaining elements 

    define start pointer that goes --> and pointer end that goes <-- to find the remaining elements 

    since the array is sorted we know when move a start or end pointer

    add the elements at position start and end and see if this + the i, j additions = target

    -3, -1, 1, 1, 1, 1, 1, 2, 4
     i   j  s  -->        <-- e
  '''
  def searchQuadruplets(self, arr, target):
    quadruplets = []
    seen = set()
    
    arr.sort()
    
    for i in range(len(arr) - 3):
      for j in range(i + 1, len(arr)
Show 1 reply
V

Victor Defontnouvelle

· 4 years ago

Seems that DP would work better here - solution would be O(n * target)

Show 1 reply
J

J

· 4 years ago

Python 3 solution appears to fail on LeetCode (4Sum)

Show 2 replies
Ratna Deep Simhadri

Ratna Deep Simhadri

· 3 years ago

For the Input [4, 1, 2, -1, 1, -3]

Target : 1

Output : [[1,4,-1,-3],[1,2,1,-3]]

Expected: [[-3,-1,1,4],[-3,1,1,2]]

Aren't both Output and Expected the Same. The Question doesn't really specify anything about Ordering the Quartet . So Both the Arrays are Same

S

shubhamrad9

· 2 years ago

import java.util.*;

class Solution {

  public List<List<Integer>> searchQuadruplets(int[] arr, int target) {
    List<List<Integer>> quadruplets = new ArrayList<>();
    Arrays.sort(arr);
    for(int i = 0; i < arr.length - 3; i++){
        while(i > 0 && arr[i-1] == arr[i]){
          continue;
        }
        findAndPushTriplet(arr, i, quadruplets, target);
    }
    return quadruplets;
  }

  public static void findAndPushTriplet(int[] arr, int firstIndex, List<List<Integer>> quadruplets, int requiredTarget){
    boolean first = true;
    int j = firstIndex + 1;
    while(j < arr.length - 2){
        
        while(!first && arr[j] == arr[j-1] && j < arr.length - 2 ){
          j++;
        } 

        int left = j+1;
        int right = arr.length - 1;
        first =
Show 1 reply
Ankit Joshi

Ankit Joshi

· a year ago

This question is exact repetition with only implementation heavy, concept is same like Triplet Sum