Four Sum
Hard Problems: N-Sum & Hashing DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Finding all unique quadruplets in an array that sum to a target value (4-sum problem), Arrays, Sorting, Two Pointers, Hash Tables, Set, Loops, Time Complexity, Space Complexity, Big O Notation, hash set, brute force, sorting algorithms, set, duplicate handling, time complexity analysis, two pointer technique, Sets & Hash Sets, Duplicate Handling in Arrays.
Problem Statement: Four Sum Given an array arr of N integers, your task is to find all unique quadruplets [arr[a], arr[b], arr[c], arr[d]] such that their sum is equal to a given target value. The indices a, b, c, and d must be distinct. Input Specification: An array of integers arr. An integer target. Output Specification: A list of unique quadruplets, where each quadruplet is a list of four integers, and the quadruplets themselves are sorted in ascending order. The elements within each quadruplet should also be sorted in ascending order. Constraints: 0 <= a, b, c, d < n a, b, c, d are distinct. arr[a] + arr[b] + arr[c] + arr[d] == target Example 1: Input: Output: Explanation: We have to find unique quadruplets from the array such that the sum of those elements is equal to the target sum given that is 0. The result obtained is such that the sum of the quadruplets yields 0. Example 2: Input: Output: Explanation: The sum of all the quadruplets is equal to the target i.e. 9.