Simple Intuitive Sliding Window Solution | O(n) Complexity
\n# Intuition\n\nTo find the k closest elements in the sorted array arr, we need to consider two conditions specified in the problem statement:\n\n1. |a - x| < 
\n# Intuition\n\nTo find the `k` closest elements in the sorted array `arr`, we need to consider two conditions specified in the problem statement:\n\n1. `|a - x| < |b - x|`, where `a` is closer to `x` than `b`.\n2. `|a - x| == |b - x|` and `a < b`, meaning if two elements have the same absolute difference, choose the smaller one.\n\nWe will use a sliding window approach to efficiently find the range of indices that satisfies both conditions. Additionally, reversing the array simplifies the logic for the second condition, where we prefer lower elements.\n\n# Approach\n\n1. **Reverse the Array**: Reverse the `nums` array to simplify processing elements from right to left, where lower elements are naturally located towards the right.\n\n2. **Initialize Pointers and Variables**: \n   - Initialize `left` to 0 (the left pointer).\n   - Initialize `minSumOfDifferences` to `Integer.MAX_VALUE` (a variable to keep track of the minimum sum of absolute differences).\n   - Initialize `sumOfDifferences` to 0 (a variable to calculate the current sum of absolute differences).\n   - Initialize `minLeft` to `left` (the left index of the minimum sum range).\n   - Initialize `minRight` to `left` (the right index of the minimum sum range).\n\n3. **Sliding Window Approach**:\n   - Iterate through the reversed `nums` array with the right pointer (`right`) from 0 to the end.\n   - Calculate the absolute difference between the current element `nums[right]` and `x` and add it to `sumOfDifferences`.\n   - Check if the window size `(right - left + 1)` is greater than or equal to `k`.\n   - If the `sumOfDifferences` is less than or equal to `minSumOfDifferences`, update `minSumOfDifferences`, `minLeft`, and `minRight`.\n   - Subtract the absolute difference between `x` and the element at the left pointer (`nums[left]`) from `sumOfDifferences` as the window slides to the right. Increment the `left` pointer.\n\n4. **Construct the Result**:\n   - After the loop, the range of indices `(minLeft, minRight)` represents the `k` closest elements with the minimum sum of absolute differences.\n   - Create a new `ArrayList` called `closestElements` to store the result.\n   - Iterate from `minRight` to `minLeft` in the reversed `nums` array and add these elements to `closestElements` in reverse order, effectively reconstructing the closest elements in ascending order.\n\n# Complexity\n- Time complexity: `O(n)`\n   - The algorithm iterates through the reversed array once to calculate the sum of absolute differences and find the range with the minimum sum. The time complexity is linear in the size of the input array.\n\n- Space complexity: `O(n)`\n   - Additional space is used to store the reversed list. The space complexity is linear in the size of the input array.\n\n# Code\n```java\nclass Solution {\n    public List<Integer> findClosestElements(int[] nums, int k, int x) {\n        // Reverse the array for easier processing\n        List<Integer> reversedList = new ArrayList<>();\n        for(int i = nums.length - 1; i >= 0; i--) reversedList.add(nums[i]);\n        // Initialize pointers and variables\n        int left = 0;                    // Left pointer\n        int minSumOfDifferences = Integer.MAX_VALUE;  // Minimum sum of differences\n        int sumOfDifferences = 0;        // Current sum of differences\n        int minLeft = left;              // Left index of the minimum sum range\n        int minRight = left;             // Right index of the minimum sum range\n\n        for (int right = 0; right < reversedList.size(); right++) {\n            sumOfDifferences += Math.abs(x - reversedList.get(right));  // Calculate the absolute difference\n            if (right - left + 1 >= k) {  // Check if the window size is greater than or equal to k\n                if (sumOfDifferences <= minSumOfDifferences) {  // Update minimum sum and indices\n                    minSumOfDifferences = sumOfDifferences;\n                    minLeft = left;\n                    minRight = right;\n                }\n                sumOfDifferences -= Math.abs(x - reversedList.get(left++));  // Subtract the left element\'s difference\n            }\n        }\n        // Construct the result\n        List<Integer> closestElements = new ArrayList<>();\n        for(int i = minRight; i >= minLeft; i--)\n         closestElements.add(reversedList.get(i));  \n        // Add elements in reverse order to get ascending order\n        return closestElements;\n    }\n}\n\n\n\n
['Sliding Window', 'Java']