Optimised Two-Pointer Approach; From 20 ms to 6 ms
This is my journey from optimising the normal two pointer approach from 20 ms to hell 6 ms! \n\n\n\n\n# Intuition\nIt happens so from handling cases of redundan
This is my journey from optimising the normal two pointer approach from 20 ms to hell 6 ms! \n\n![Screenshot 2024-03-09 at 7.39.45 PM.png](https://assets.leetcode.com/users/images/c736609f-0473-4ece-8723-b7c876ca1550_1709994682.1960773.png)\n\n\n# Intuition\nIt happens so from handling cases of redundant iterations.\nFor example,\nYou break out of the first loop if target is greater than zero and first four elements sum from first index is greater than target.\nThere are two more conditions for breaking if target is less or another - is equal to zero.\n\nThere are soo many and I explain them properly with comments.\n\n# Approach\nI present you the speciifc section for optimising.\n```\n            for (int i = 0; i < n - 3; i++) {\n            // Skip duplicates for the first element\n            if (i > 0 && nums[i] == nums[i - 1]) {\n                continue; \n            }\n            // Early exit if the sum of the first four smallest elements is greater than the target (for positive target)\n            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target && target > 0) {\n                break;\n            }\n            // Early exit if the sum of the first four smallest elements is greater than the target (for negative target)\n            if(nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target && target < 0 && i + 4 < n && nums[i + 4] > 0) {\n                break;\n            }\n            // Early exit if the target is zero and there are positive numbers after the first four smallest elements\n            if(target == 0 && i + 4 < n && nums[i + 4] > 0 && nums[i] > 0) {\n                break;          \n            }\n            // Early continue if the sum of the first element and the three largest elements is less than the target (for positive target)\n            if ((long)nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target && target > 0) {\n                continue;\n            }\n            // Iterate through array for potential second element of quadruplet\n            for (int j = i + 1; j < n - 2; j++) {\n                // Skip duplicates for the second element\n                if (j > i + 1 && nums[j] == nums[j - 1]) {\n                    continue; \n                }\n                // Early continue if the sum of the first two elements and the two largest elements is less than the target (for non-negative target)\n                if ((long)nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target && target >= 0) {\n                    continue;\n```\n\n# Complexity\n- Time complexity:\nSame as normal - 0(n^3)\n- Space complexity:\n0(1)\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        Arrays.sort(nums); // Sort the input array to simplify the search\n        \n        List<List<Integer>> result = new ArrayList<>(); // List to store the quadruplets\n        \n        int n = nums.length;\n        \n        // Iterate through the array, fixing the first element of the quadruplet\n        for (int i = 0; i < n - 3; i++) {\n            // Skip duplicates\n            if (i > 0 && nums[i] == nums[i - 1]) {\n                continue; \n            }\n            \n            // Early exit condition if the sum of the first four elements is greater than the target (for positive targets)\n            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target && target > 0) {\n                break;\n            }\n            \n            // Early exit condition if the sum of the first four elements is greater than the target (for negative targets with positive elements)\n            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target && target < 0 && i + 4 < n && nums[i + 4] > 0) {\n                break;\n            }\n            \n            // Early exit condition if the target is zero and there are positive numbers after the first four smallest elements\n            if (target == 0 && i + 4 < n && nums[i + 4] > 0 && nums[i] > 0) {\n                break;          \n            }         \n            \n            // Early continue if the sum of the first element and the three largest elements is less than the target\n            if ((long) nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target && target > 0) {\n                continue;\n            }\n            \n            // Iterate through the remaining elements using a two-pointer approach\n            for (int j = i + 1; j < n - 2; j++) {\n                // Skip duplicates\n                if (j > i + 1 && nums[j] == nums[j - 1]) {\n                    continue; \n                }\n                \n                // Early exit condition if the target is zero and there are positive numbers after the first two smallest elements\n                if (j < n - 1 && nums[j] > 0 && nums[j + 1] > 0 && target - nums[i] == 0) {\n                    break;\n                }\n                \n                // Early exit condition if the sum of the first three elements and the largest element is greater than the target\n                if (target > 0 && nums[i] + nums[j] + nums[j + 1] > target - nums[i]) {\n                    break;\n                }\n                \n                // Early exit condition if the sum of the first three elements and the largest positive element is less than the target\n                if (target < 0 && nums[i] + nums[j] + nums[j + 1] > target - nums[i] && j + 2 < n && nums[j + 2] > 0) {\n                    break;\n                }\n                \n                // Early continue if the sum of the first two elements and the two largest elements is less than the target\n                if ((long) nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target && target >= 0) {\n                    continue;\n                }\n\n                int left = j + 1; // Initialize left pointer\n                int right = n - 1; // Initialize right pointer\n                \n                // Two-pointer approach to find the remaining two elements\n                while (left < right) {\n                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; // Calculate the sum\n                    \n                    if (sum == target) { // Quadruplet found\n                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // Add quadruplet to result\n                        \n                        // Skip duplicates\n                        while (left < right && nums[left] == nums[left + 1]) {\n                            left++;\n                        }\n                        while (left < right && nums[right] == nums[right - 1]) {\n                            right--;\n                        }\n                        \n                        left++; // Move left pointer\n                        right--; // Move right pointer\n                    } else if (sum < target) { // If sum is less than target, move left pointer to increase sum\n                        left++;\n                    } else { // If sum is greater than target, move right pointer to decrease sum\n                        right--;\n                    }\n                }\n            }\n        }\n        \n        return result; // Return the list of quadruplets\n    }\n}\n\n\n```\n\nBelow is the history of optimising from 20 ms to 6 gradually haha\n\n![Screenshot 2024-03-09 at 7.40.38 PM.png](https://assets.leetcode.com/users/images/3ce5d71b-f119-4b63-8fa0-e7f1569e0bf8_1709994745.426009.png)\n\n
['Two Pointers', 'Java']