Four Sum

In this class, We discuss the Four Sum.

Readers can prepare an entire competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given an array of integers and an integer value.

Find all the unique quadruples in the array that sum to the given number.

Example:

Input: [10,2,3,4,5,7,8] and K = 23

Output: [2,3,8,10],[2,4,7,10],[3,5,7,8]

Time complexity O(N^3)

Space complexity O(N)

Logic:

Our previous examples discussed selecting all possible two-number combinations in an array.

We use a two-level loop to select all combinations.

Similarly, a three-level loop to select all three element combinations.

Three level loop time complexity is O(N^3)

Similarly, a four-level loop is to select all quadruples.

Four level loop will have a time complexity of O(N^4)

By using hashing, we can reduce the time to O(N^3)

The step-by-step explanation is provided in the video.

Code: