⚕️[EASY] INTUITION & EXPLANATION
\n\n# \uD83D\uDC93**_PLEASE CONSIDER UPVOTING_**\uD83D\uDC93\n\n \n\n\n# \u2B50 Intuition\nThe problem asks for finding all unique quadruplets (four numbers) in
<div align="center">\n\n# \uD83D\uDC93**_PLEASE CONSIDER UPVOTING_**\uD83D\uDC93\n\n</div>\n\n***\n# \u2B50 Intuition\nThe problem asks for finding all unique quadruplets (four numbers) in an array that add up to a given target. A brute force approach would involve checking every combination of four numbers, but this would be inefficient. Instead, we can leverage sorting and the two-pointer technique, which is often used for the 3-sum problem, to optimize the search for quadruplets.\n\n# \u2B50 Approach\n1. **Sort the array**: Sorting helps in efficiently applying the two-pointer technique and also allows us to skip duplicate elements.\n2. **Two loops for the first two numbers**:\n   - Use two nested loops: the outer loop iterates over the first element of the quadruplet (`i`), and the inner loop iterates over the second element (`j`).\n   - Skip duplicate elements in both loops to avoid generating duplicate quadruplets.\n3. **Two-pointer technique for the remaining two numbers**:\n   - For the remaining two numbers, use a two-pointer approach:\n     - Start one pointer `k` from just after `j` and another pointer `l` from the end of the array.\n     - Calculate the sum of the four elements: `arr[i] + arr[j] + arr[k] + arr[l]`.\n     - If the sum equals the target, add the quadruplet to the result and move both pointers inward while skipping duplicates.\n     - If the sum is less than the target, move the left pointer (`k`) to increase the sum.\n     - If the sum is greater than the target, move the right pointer (`l`) to decrease the sum.\n4. **Return the result**: The result list contains all unique quadruplets whose sum equals the target.\n\n# \u2B50 Complexity\n- **Time complexity:**  \n  Sorting the array takes $$O(n \\log n)$$, and we use two nested loops and a two-pointer technique, which results in a total time complexity of $$O(n^3)$$, where $$n$$ is the length of the array.\n\n- **Space complexity:**  \n  The space complexity is $$O(1)$$ for extra space since we only use a few variables for the two-pointer technique. However, the space complexity for the result list will depend on the number of quadruplets found.\n\n# \u2B50 Code\n```java\nclass Solution {\n    public List<List<Integer>> fourSum(int[] arr, int target) {\n        List<List<Integer>> ans = new ArrayList<>();\n        int len = arr.length;\n\n        Arrays.sort(arr);\n\n        for (int i = 0; i < len - 3; i++) {\n            if (i > 0 && arr[i - 1] == arr[i]) continue;\n\n            for (int j = i + 1; j < len - 2; j++) {\n                if (j > i + 1 && arr[j - 1] == arr[j]) continue;\n\n                int k = j + 1;\n                int l = len - 1;\n\n                while (k < l) {\n                    long sum = arr[i] + arr[j];\n                    sum += arr[k] + arr[l];\n\n                    if (sum == target) {\n                        ans.add(Arrays.asList(arr[i], arr[j], arr[k], arr[l]));\n                        k++;\n                        l--;\n                        while (k < l && arr[k - 1] == arr[k]) k++;\n                        while (k < l && arr[l + 1] == arr[l]) l--;\n                    } else if (sum < target) {\n                        k++;\n                    } else {\n                        l--;\n                    }\n                }\n            }\n        }\n\n        return ans;\n    }\n}\n```
['Array', 'Two Pointers', 'Sorting', 'Java']