✅6 Method's || C++ || JAVA || PYTHON ||✅ 100% beat  || Beginner Friendly🔥🔥🔥
 Method 1 \nIntuition\nThe problem is about finding the k closest elements to a given integer x from a sorted array. The elements should be as close as possible
# **<bold><center> Method 1 </center></bold>**\n**Intuition**\nThe problem is about finding the `k` closest elements to a given integer `x` from a sorted array. The elements should be as close as possible to `x`, and in the case of ties (where two elements have the same difference from `x`), the smaller element should be chosen. The final result should also be sorted.\n\n**Approach**\n\n1. **Sorting Approach**: First, sort the array based on the absolute difference from `x`. If two elements have the same difference, sort them by their value. After sorting, pick the first `k` elements and sort them again to get the final answer.\n\n**Detailed Walkthrough**\n\n1. **Step 1**: Use a custom sorting function to sort the array based on the difference from `x`. If two elements have the same difference, sort by their values.\n  \n2. **Step 2**: After sorting, the first `k` elements are the closest to `x`. Extract these elements.\n\n3. **Step 3**: Finally, sort the extracted elements to return the result in ascending order.\n\n**Dry Run**\n\nFor `arr = [1, 2, 3, 4, 5]`, `k = 4`, and `x = 3`:\n\n1. After custom sorting based on proximity to `3`: `[3, 2, 4, 1, 5]`\n2. Extract the first `k` elements: `[3, 2, 4, 1]`\n3. Sort these elements to get the final result: `[1, 2, 3, 4]`\n\n**Code**\n\n```cpp []\n#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int> sorting(vector<int> nums, int k, int x) {\n    sort(nums.begin(), nums.end(), [x](int a, int b) {\n        if (abs(a - x) == abs(b - x)) {\n            return a < b;\n        }\n        return abs(a - x) < abs(b - x);\n    });\n    vector<int> ans(nums.begin(), nums.begin() + k);\n    sort(ans.begin(), ans.end());\n    return ans;\n}\n```\n\n```python []\ndef sorting(nums, k, x):\n    nums.sort(key=lambda num: (abs(num - x), num))\n    ans = sorted(nums[:k])\n    return ans\n\n# Example usage:\nnums = [10, 15, 7, 3, 4]\nk = 3\nx = 8\nprint(sorting(nums, k, x))  # Output: [7, 10, 15]\n\n```\n```Java []\nimport java.util.*;\n\npublic class Main {\n    public static List<Integer> sorting(List<Integer> nums, int k, int x) {\n        nums.sort((a, b) -> {\n            if (Math.abs(a - x) == Math.abs(b - x)) {\n                return Integer.compare(a, b);\n            }\n            return Integer.compare(Math.abs(a - x), Math.abs(b - x));\n        });\n        List<Integer> ans = new ArrayList<>(nums.subList(0, k));\n        Collections.sort(ans);\n        return ans;\n    }\n\n    public static void main(String[] args) {\n        List<Integer> nums = Arrays.asList(10, 15, 7, 3, 4);\n        int k = 3;\n        int x = 8;\n        System.out.println(sorting(nums, k, x));  // Output: [7, 10, 15]\n    }\n}\n\n```\n\n**Complexity Analysis**\n\n- **Time Complexity**: $$( O(n \\log n) $$, where `n` is the number of elements in the array. The main time complexity comes from sorting the array.\n- **Space Complexity**: $$( O(k) $$, for storing the result.\n\n**Summary**\n\nThe sorting approach sorts the array based on the difference from `x` and selects the first `k` elements. This method ensures that we get the closest elements to `x`, and it handles ties by choosing the smaller elements. The final result is sorted in ascending order before being returned. This approach efficiently solves the problem, with a clear and straightforward implementation.\n\n<br>\n<br>\n\n# **<bold><center> Method 2 </center></bold>**\n**Intuition**\n\nThe problem asks for finding the `k` closest integers to a given number `x` in a sorted array. The key observation here is that because the array is sorted, the closest elements will be near the position where `x` would be if it were present in the array. The goal is to find those `k` closest elements efficiently.\n\n**Approach**\n\n1. **Two-Pointer Brute Force Approach**: \n   - First, find the element in the array that is closest to `x`. This gives a good starting point.\n   - Then, use two pointers, one moving left and the other moving right from this starting point, to find the `k` closest elements.\n   - Finally, sort the resulting `k` elements before returning them to ensure they are in ascending order.\n\n**Detailed Walkthrough**\n\n1. **Step 1**: Calculate the difference between each element in the array and `x`. Store these differences in a `diff` array.\n  \n2. **Step 2**: Identify the element with the smallest difference. This will be the closest element to `x`.\n\n3. **Step 3**: Use two pointers, `left` and `right`, to expand from this closest element. Compare the elements on the left and right sides and choose the one that is closer to `x`. Repeat this process until you have selected `k` elements.\n\n4. **Step 4**: Once the `k` closest elements are selected, sort them to get the final result in ascending order.\n\n**Dry Run**\n\nFor `arr = [1, 2, 3, 4, 5]`, `k = 4`, and `x = 3`:\n\n1. **Step 1**: Calculate differences: `[2, 1, 0, 1, 2]`\n2. **Step 2**: Find the closest element: `3` at index `2`.\n3. **Step 3**: Expand using two pointers:\n   - Initial: Closest element `3`\n   - Next closest: `2` (left)\n   - Next closest: `4` (right)\n   - Next closest: `1` (left)\n4. **Step 4**: Sort the selected elements: `[1, 2, 3, 4]`\n\n**Code**\n\n```cpp []\n#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int> min_using_two_pointer_brute_force(vector<int> nums, int k, int x){\n    vector<int> diff(nums.size());\n    for(int i = 0; i < nums.size(); i++){\n        diff[i] = abs(nums[i] - x);\n    }\n\n    int minimum = INT_MAX, min_index = -1;\n    for(int i = 0; i < nums.size(); i++){\n        if(minimum > diff[i]){\n            minimum = diff[i];\n            min_index = i;\n        }\n    }\n    vector<int> ans;\n    ans.push_back(nums[min_index]);\n    int left = min_index - 1;\n    int right = min_index + 1;\n    for (int i = 1; i < k; i++) {\n        if (left < 0) {\n            ans.push_back(nums[right++]);\n        } else if (right >= nums.size()) {\n            ans.push_back(nums[left--]);\n        } else if (diff[left] <= diff[right]) {\n            ans.push_back(nums[left--]);\n        } else {\n            ans.push_back(nums[right++]);\n        }\n    }\n\n    sort(ans.begin(), ans.end());\n    return ans;\n}\n```\n```python []\ndef min_using_two_pointer_brute_force(nums, k, x):\n    diff = [abs(num - x) for num in nums]\n\n    minimum = float(\'inf\')\n    min_index = -1\n    for i in range(len(nums)):\n        if minimum > diff[i]:\n            minimum = diff[i]\n            min_index = i\n\n    ans = [nums[min_index]]\n    left = min_index - 1\n    right = min_index + 1\n    for i in range(1, k):\n        if left < 0:\n            ans.append(nums[right])\n            right += 1\n        elif right >= len(nums):\n            ans.append(nums[left])\n            left -= 1\n        elif diff[left] <= diff[right]:\n            ans.append(nums[left])\n            left -= 1\n        else:\n            ans.append(nums[right])\n            right += 1\n\n    ans.sort()\n    return ans\n\n# Example usage:\nnums = [10, 15, 7, 3, 4]\nk = 3\nx = 8\nprint(min_using_two_pointer_brute_force(nums, k, x))  # Output: [7, 10, 15]\n```\n```Java []\nimport java.util.*;\n\npublic class Main {\n    public static List<Integer> min_using_two_pointer_brute_force(List<Integer> nums, int k, int x) {\n        List<Integer> diff = new ArrayList<>();\n        for (int num : nums) {\n            diff.add(Math.abs(num - x));\n        }\n\n        int minimum = Integer.MAX_VALUE;\n        int min_index = -1;\n        for (int i = 0; i < nums.size(); i++) {\n            if (minimum > diff.get(i)) {\n                minimum = diff.get(i);\n                min_index = i;\n            }\n        }\n\n        List<Integer> ans = new ArrayList<>();\n        ans.add(nums.get(min_index));\n        int left = min_index - 1;\n        int right = min_index + 1;\n        for (int i = 1; i < k; i++) {\n            if (left < 0) {\n                ans.add(nums.get(right++));\n            } else if (right >= nums.size()) {\n                ans.add(nums.get(left--));\n            } else if (diff.get(left) <= diff.get(right)) {\n                ans.add(nums.get(left--));\n            } else {\n                ans.add(nums.get(right++));\n            }\n        }\n\n        Collections.sort(ans);\n        return ans;\n    }\n\n    public static void main(String[] args) {\n        List<Integer> nums = Arrays.asList(10, 15, 7, 3, 4);\n        int k = 3;\n        int x = 8;\n        System.out.println(min_using_two_pointer_brute_force(nums, k, x));  // Output: [7, 10, 15]\n    }\n}\n\n```\n**Complexity Analysis**\n\n- **Time Complexity**: \n  - Calculating differences: $$ O(n) $$\n  - Finding the minimum difference: $$ O(n) $$\n  - Two-pointer expansion to find `k` elements: $$ O(k) $$\n  - Final sorting of `k` elements: $$ O(k \\log k) $$\n  - **Overall**: $$ O(n + k \\log k) $$\n  \n- **Space Complexity**: $$( O(n) $$) for the `diff` array and the `ans` vector.\n\n**Summary**\n\nThe two-pointer brute force approach is an intuitive way to solve the problem by leveraging the fact that the array is sorted. We first locate the closest element and then use two pointers to collect the next closest elements. The approach ensures that we get the exact `k` closest elements efficiently, even if the final sorting step adds some overhead. This method is especially useful for understanding how to balance simplicity with performance in algorithm design.\n\n# *Method 3*\n**\uD83E\uDDE0 Intuition**\n\nThe problem is to find the `k` closest elements to a given integer `x` from a sorted array. We can leverage the fact that the array is sorted to efficiently determine which elements are closest to `x`. A max-heap (priority queue) is useful here because it allows us to maintain a set of the `k` closest elements as we iterate through the array. By storing the elements in the heap based on their distance from `x`, we can efficiently determine which elements to keep and which to discard.\n\n**\uD83D\uDEE0\uFE0F Approach**\n\n1. **Max-Heap (Priority Queue) Approach**:\n   - Use a max-heap to maintain the closest `k` elements. The heap will store pairs of `(distance, element)` where `distance` is the absolute difference between `element` and `x`.\n   - As we iterate through the array, we push each element\'s distance and value into the heap.\n   - If the size of the heap exceeds `k`, we remove the element with the largest distance (i.e., the least close) to ensure we only keep the `k` closest elements.\n   - Finally, extract the elements from the heap, sort them, and return the result.\n\n**\uD83D\uDEB6 Detailed Walkthrough**\n\n1. **Step 1**: Initialize a max-heap (priority queue) that will store pairs of `(distance, element)`. The `distance` is calculated as `abs(nums[i] - x)`.\n\n2. **Step 2**: Iterate through each element in the array:\n   - Calculate the distance from `x` for the current element.\n   - Push this pair `(distance, element)` into the heap.\n   - If the size of the heap exceeds `k`, pop the top element (which is the one with the maximum distance) from the heap.\n\n3. **Step 3**: After iterating through the array, the heap contains the `k` closest elements. Extract these elements and store them in a result array.\n\n4. **Step 4**: Sort the result array to meet the requirement of returning the elements in ascending order.\n\n5. **Step 5**: Return the sorted result array.\n\n**\uD83E\uDDEA Dry Run**\n\nFor `arr = [1, 2, 3, 4, 5]`, `k = 4`, and `x = 3`:\n\n1. **Step 1**: Initialize an empty max-heap.\n2. **Step 2**:\n   - Insert `(2, 1)` into the heap: `[(2, 1)]`\n   - Insert `(1, 2)` into the heap: `[(2, 1), (1, 2)]`\n   - Insert `(0, 3)` into the heap: `[(2, 1), (1, 2), (0, 3)]`\n   - Insert `(1, 4)` into the heap: `[(2, 1), (1, 2), (0, 3), (1, 4)]`\n   - Insert `(2, 5)` into the heap and pop the max element: `[(1, 2), (1, 4), (0, 3), (2, 5)]` (after popping `(2, 1)`)\n3. **Step 3**: Extract elements from the heap: `[2, 4, 3, 5]`\n4. **Step 4**: Sort the array: `[1, 2, 3, 4]`\n5. **Step 5**: Return `[1, 2, 3, 4]`\n\n**\uD83D\uDCBB Code**\n\n```cpp []\n#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int> closet_element_using_queue(vector<int> nums, int k, int x){\n    priority_queue<pair<int,int>, vector<pair<int,int>>, less<pair<int, int>>>pq;\n    for(int i = 0; i < nums.size(); i++){\n        int dist = abs(nums[i] - x);\n        pq.push({dist, nums[i]});\n        if(pq.size() > k){\n            pq.pop();\n        }\n    }\n\n    vector<int> res;\n    for(int i=0; i < k; i++){\n        res.push_back(pq.top().second);\n        pq.pop();\n    }\n    sort(res.begin(), res.end());\n\n    return res;\n}\n```\n```python []\nimport heapq\n\ndef closet_element_using_queue(nums, k, x):\n    pq = []\n    for num in nums:\n        dist = abs(num - x)\n        heapq.heappush(pq, (-dist, -num))  # Push negative to simulate max-heap\n        if len(pq) > k:\n            heapq.heappop(pq)\n\n    res = [-heapq.heappop(pq)[1] for _ in range(k)]\n    res.sort()\n    return res\n\n# Example usage:\nnums = [10, 15, 7, 3, 4]\nk = 3\nx = 8\nprint(closet_element_using_queue(nums, k, x))  # Output: [7, 10, 15]\n\n```\n```java []\nimport java.util.*;\n\npublic class Main {\n    public static List<Integer> closet_element_using_queue(List<Integer> nums, int k, int x) {\n        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> {\n            if (a.dist == b.dist) {\n                return b.value - a.value;\n            }\n            return b.dist - a.dist;\n        });\n\n        for (int num : nums) {\n            int dist = Math.abs(num - x);\n            pq.offer(new Pair(dist, num));\n            if (pq.size() > k) {\n                pq.poll();\n            }\n        }\n\n        List<Integer> res = new ArrayList<>();\n        for (int i = 0; i < k; i++) {\n            res.add(pq.poll().value);\n        }\n        Collections.sort(res);\n        return res;\n    }\n\n    static class Pair {\n        int dist;\n        int value;\n\n        Pair(int dist, int value) {\n            this.dist = dist;\n            this.value = value;\n        }\n    }\n\n    public static void main(String[] args) {\n        List<Integer> nums = Arrays.asList(10, 15, 7, 3, 4);\n        int k = 3;\n        int x = 8;\n        System.out.println(closet_element_using_queue(nums, k, x));  // Output: [7, 10, 15]\n    }\n}\n\n```\n**\uD83D\uDCCA Complexity Analysis**\n\n- **Time Complexity**:\n  - Building the heap and maintaining its size: \\( O(n \\log k) \\) where `n` is the number of elements in the array.\n  - Sorting the final `k` elements: \\( O(k \\log k) \\).\n  - **Overall**: \\( O(n \\log k + k \\log k) \\).\n  \n- **Space Complexity**:\n  - The heap requires \\( O(k) \\) space to store the closest elements.\n  - The result array also takes \\( O(k) \\) space.\n  - **Overall**: \\( O(k) \\).\n\n**\u2728 Summary**\n\nThe max-heap approach is a clever way to find the `k` closest elements to `x` in a sorted array by focusing on maintaining the closest elements during the iteration. This approach is particularly useful when the value of `k` is small compared to the size of the array. The heap efficiently handles the insertion and removal of elements, ensuring that only the closest elements are kept. Finally, sorting the result provides the final output in ascending order, satisfying the problem constraints.\n\n# **Method 4**\n**\uD83E\uDDE0 Intuition**\n\nIn this problem, we need to find the `k` closest integers to a given value `x` in a sorted array. We can leverage the sorted property of the array to efficiently narrow down the range of elements that are closest to `x`. By using a two-pointer technique, we can compare elements from both ends of the array and gradually eliminate the elements that are farther from `x`. This approach allows us to directly find the desired `k` elements without sorting or extra data structures.\n\n**\uD83D\uDEE0\uFE0F Approach**\n\n1. **Two-Pointer Approach**:\n   - Use two pointers, `left` starting from the beginning of the array and `right` starting from the end.\n   - The goal is to shrink the range `[left, right]` until the range has exactly `k` elements.\n   - At each step, compare the difference between `x` and the elements at `left` and `right`.\n   - If the element at `left` is farther from `x` than the element at `right`, move the `left` pointer to the right (i.e., `left++`).\n   - Otherwise, move the `right` pointer to the left (i.e., `right--`).\n   - Once the range has `k` elements, return that subarray.\n\n**\uD83D\uDEB6 Detailed Walkthrough**\n\n1. **Step 1**: Initialize two pointers: `left` at the start (`0`) and `right` at the end (`n-1`) of the array.\n\n2. **Step 2**: Enter a loop where you check the size of the current window `[left, right]`. If the window size is greater than `k`, compare the distance between `x` and the elements at `left` and `right`.\n   - If the element at `left` is farther from `x` than the element at `right`, move the `left` pointer to the right (`left++`).\n   - Otherwise, move the `right` pointer to the left (`right--`).\n\n3. **Step 3**: The loop continues until `right - left + 1 == k`. At this point, the subarray `[left, right]` contains the `k` closest elements.\n\n4. **Step 4**: Return the subarray from index `left` to `left + k`.\n\n**\uD83E\uDDEA Dry Run**\n\nFor `arr = [1, 2, 3, 4, 5]`, `k = 4`, and `x = 3`:\n\n1. **Initial Pointers**:\n   - `left = 0`, `right = 4`\n   \n2. **Iteration 1**:\n   - Compare `x - arr[left]` (`3 - 1 = 2`) and `arr[right] - x` (`5 - 3 = 2`).\n   - Since the distances are equal, move `right` pointer: `right = 3`.\n\n3. **Iteration 2**:\n   - Compare `x - arr[left]` (`3 - 1 = 2`) and `arr[right] - x` (`4 - 3 = 1`).\n   - Move `left` pointer: `left = 1`.\n\n4. **Iteration 3**:\n   - Compare `x - arr[left]` (`3 - 2 = 1`) and `arr[right] - x` (`4 - 3 = 1`).\n   - Move `right` pointer: `right = 2`.\n\n5. **Final State**:\n   - Subarray `[left, right] = [1, 2, 3, 4]` is the result.\n\n**\uD83D\uDCBB Code**\n\n```cpp []\nvector<int> two_pointer(vector<int> &nums, int k , int x){\n    int left = 0, right = nums.size() - 1;\n    while(right - left >= k )\n        if(x - nums[left] > nums[right] - x)\n            left++;\n        else\n            right--;\n    return vector<int> (nums.begin()+left, nums.begin()+left+k);\n}\n```\n```python []\ndef two_pointer(nums, k, x):\n    left, right = 0, len(nums) - 1\n    while right - left >= k:\n        if x - nums[left] > nums[right] - x:\n            left += 1\n        else:\n            right -= 1\n    return nums[left:left + k]\n\n# Example usage:\nnums = [1, 2, 3, 4, 5]\nk = 3\nx = 3\nprint(two_pointer(nums, k, x))  # Output: [2, 3, 4]\n\n```\n```Java []\nimport java.util.*;\n\npublic class Main {\n    public static List<Integer> two_pointer(List<Integer> nums, int k, int x) {\n        int left = 0, right = nums.size() - 1;\n        while (right - left >= k) {\n            if (x - nums.get(left) > nums.get(right) - x) {\n                left++;\n            } else {\n                right--;\n            }\n        }\n        return nums.subList(left, left + k);\n    }\n\n    public static void main(String[] args) {\n        List<Integer> nums = Arrays.asList(1, 2, 3, 4, 5);\n        int k = 3;\n        int x = 3;\n        System.out.println(two_pointer(nums, k, x));  // Output: [2, 3, 4]\n    }\n}\n\n```\n**\uD83D\uDCCA Complexity Analysis**\n\n- **Time Complexity**:\n  - The algorithm runs in `O(n)` time, where `n` is the size of the array. This is because the two-pointer technique iterates through the array once, adjusting the pointers until the correct subarray of size `k` is found.\n  \n- **Space Complexity**:\n  - The space complexity is `O(1)` for the pointers, plus `O(k)` for the result subarray, leading to an overall space complexity of `O(k)`.\n\n**\u2728 Summary**\n\nThe two-pointer approach provides an efficient way to find the `k` closest elements to `x` in a sorted array by leveraging the sorted order and directly comparing the elements from both ends of the array. This method ensures that only the closest elements are considered, and the result is obtained without needing to sort or use extra data structures, making it both time and space-efficient.\n\n# **Method 5**\n**\uD83E\uDDE0 Intuition**\n\nThe goal is to find the `k` closest elements to a given integer `x` in a sorted array. To achieve this efficiently, we can utilize binary search to quickly locate the position of `x` (or the closest element to `x` if it doesn\'t exist) in the array. Then, we can expand outwards using two pointers to capture the `k` closest elements. This approach combines the efficiency of binary search with the flexibility of the two-pointer technique, allowing us to handle the problem with minimal complexity.\n\n**\uD83D\uDEE0\uFE0F Approach**\n\n1. **Binary Search for Closest Position**:\n   - Use `lower_bound` to find the position `h` where `x` would be inserted in the array while maintaining sorted order.\n   - This gives us a starting point where `x` might be located, or the nearest greater element.\n\n2. **Two-Pointer Expansion**:\n   - Initialize two pointers: `l` at `h-1` (left of `h`) and `h` itself.\n   - Gradually expand these pointers outward to collect the `k` closest elements.\n   - At each step, compare the distance between `x` and the elements at `l` and `h`.\n   - Move the pointer that points to the element farther from `x`.\n\n3. **Return Result**:\n   - Once `k` elements are collected, return the subarray from `l+1` to `h` (this range will have exactly `k` elements).\n\n**\uD83D\uDEB6 Detailed Walkthrough**\n\n1. **Step 1**: Perform a binary search to locate the closest position `h` where `x` would be inserted. This is achieved using `lower_bound(nums.begin(), nums.end(), x)`.\n\n2. **Step 2**: Initialize two pointers:\n   - `h` at the position found by `lower_bound`.\n   - `l` just before `h` (`l = h - 1`).\n\n3. **Step 3**: Enter a loop that continues for `k` iterations:\n   - Compare `x - nums[l]` with `nums[h] - x`.\n   - If the element at `l` is farther, decrement `l`.\n   - If the element at `h` is farther, increment `h`.\n   - This ensures that the closest elements are chosen.\n\n4. **Step 4**: Once the loop completes, return the subarray `[l + 1, h)`. This range contains the `k` closest elements.\n\n**\uD83E\uDDEA Dry Run**\n\nFor `arr = [1, 2, 3, 4, 5]`, `k = 4`, and `x = 3`:\n\n1. **Initial Search**:\n   - Binary search finds `h = 2` (`nums[h] = 3`).\n\n2. **Pointer Initialization**:\n   - `l = 1` (`nums[l] = 2`), `h = 2` (`nums[h] = 3`).\n\n3. **Iteration 1**:\n   - Compare `x - nums[l]` (`3 - 2 = 1`) with `nums[h] - x` (`3 - 3 = 0`).\n   - Increment `h` since `h` is closer: `h = 3`.\n\n4. **Iteration 2**:\n   - Compare `x - nums[l]` (`3 - 2 = 1`) with `nums[h] - x` (`4 - 3 = 1`).\n   - Decrement `l` since distances are equal: `l = 0`.\n\n5. **Iteration 3**:\n   - Compare `x - nums[l]` (`3 - 1 = 2`) with `nums[h] - x` (`4 - 3 = 1`).\n   - Increment `h`: `h = 4`.\n\n6. **Iteration 4**:\n   - Compare `x - nums[l]` (`3 - 1 = 2`) with `nums[h] - x` (`5 - 3 = 2`).\n   - Increment `h`: `h = 5`.\n\n7. **Final State**:\n   - Return subarray `[l + 1, h) = [1, 2, 3, 4]`.\n\n**\uD83D\uDCBB Code**\n\n```cpp []\nvector<int> bs_plus_two_pointer_method(vector<int>& nums, int k ,int x){\n    int h = lower_bound(nums.begin(), nums.end(), x) - nums.begin();\n    int l = h-1;\n    while(k--){\n        if(x - nums[l] > nums[h] - x)\n            h++;\n        else\n            l--;\n    }\n    return vector<int> (nums.begin()+l+1, nums.begin() + h);\n}\n```\n``` python []\nimport bisect\n\ndef bs_plus_two_pointer_method(nums, k, x):\n    h = bisect.bisect_left(nums, x)\n    l = h - 1\n    while k > 0:\n        if l < 0:\n            h += 1\n        elif h >= len(nums) or x - nums[l] <= nums[h] - x:\n            l -= 1\n        else:\n            h += 1\n        k -= 1\n    return nums[l + 1:h]\n\n# Example usage:\nnums = [1, 2, 3, 4, 5]\nk = 3\nx = 3\nprint(bs_plus_two_pointer_method(nums, k, x))  # Output: [2, 3, 4]\n\n```\n``` java []\nimport java.util.*;\n\npublic class Main {\n    public static List<Integer> bs_plus_two_pointer_method(List<Integer> nums, int k, int x) {\n        int h = Collections.binarySearch(nums, x);\n        if (h < 0) {\n            h = -h - 1;  // Adjust the insertion point from binarySearch result\n        }\n        int l = h - 1;\n        while (k-- > 0) {\n            if (l < 0) {\n                h++;\n            } else if (h >= nums.size() || x - nums.get(l) <= nums.get(h) - x) {\n                l--;\n            } else {\n                h++;\n            }\n        }\n        return nums.subList(l + 1, h);\n    }\n\n    public static void main(String[] args) {\n        List<Integer> nums = Arrays.asList(1, 2, 3, 4, 5);\n        int k = 3;\n        int x = 3;\n        System.out.println(bs_plus_two_pointer_method(nums, k, x));  // Output: [2, 3, 4]\n    }\n}\n\n```\n**\uD83D\uDCCA Complexity Analysis**\n\n- **Time Complexity**:\n  - Binary search takes `O(log n)`, and the two-pointer technique takes `O(k)` time to find the `k` closest elements. Therefore, the overall time complexity is `O(log n + k)`.\n\n- **Space Complexity**:\n  - The space complexity is `O(k)` for storing the result, as the algorithm only uses a few additional pointers.\n\n**\u2728 Summary**\n\nThis method effectively combines the strengths of binary search and the two-pointer technique to find the `k` closest elements to `x` in a sorted array. By first narrowing down the potential closest elements using binary search and then refining the selection using two pointers, we achieve a highly efficient solution that works well even for large arrays.\n\n# **Method 6**(Most Optimal)\n**\uD83E\uDDE0 Intuition**\n\nThe problem is to find the `k` closest elements to `x` in a sorted array. To solve this efficiently, we can leverage binary search to find the best starting point for the `k` closest elements. Instead of finding the exact position of `x`, we aim to identify the range of `k` elements that are closest to `x` by comparing the potential ranges in a binary search fashion.\n\n**\uD83D\uDEE0\uFE0F Approach**\n\n1. **Binary Search**:\n   - We are interested in finding the best starting point `left` such that the subarray `[left, left + k - 1]` contains the `k` closest elements to `x`.\n   - The search range for `left` is from `0` to `A.size() - k`.\n\n2. **Comparison Logic**:\n   - During the binary search, at each step, we compare the distances between `x` and the elements at the current `mid` and `mid + k`.\n   - If `A[mid]` is farther from `x` than `A[mid + k]`, then we move `left` to `mid + 1`. Otherwise, we move `right` to `mid`.\n\n3. **Result Extraction**:\n   - After narrowing down the range, the best starting index `left` is found.\n   - Return the subarray `[left, left + k)` as the result.\n\n**\uD83D\uDEB6 Detailed Walkthrough**\n\n1. **Initialize Search Boundaries**:\n   - `left` is initialized to `0` (the beginning of the array).\n   - `right` is initialized to `A.size() - k` (ensuring that `left + k` does not exceed the array\'s bounds).\n\n2. **Binary Search**:\n   - While `left < right`, compute `mid` as `(left + right) / 2`.\n   - Compare `x - A[mid]` with `A[mid + k] - x`.\n     - If `x - A[mid]` is greater, move `left` to `mid + 1` (this means the subarray starting at `mid + 1` might be closer to `x`).\n     - Otherwise, move `right` to `mid`.\n\n3. **Extract the Subarray**:\n   - Once `left` equals `right`, the loop terminates.\n   - The subarray starting from `left` with length `k` contains the `k` closest elements.\n\n**\uD83E\uDDEA Dry Run**\n\nFor `arr = [1, 2, 3, 4, 5]`, `k = 4`, and `x = 3`:\n\n1. **Initialization**:\n   - `left = 0`, `right = 1` (`A.size() - k = 5 - 4 = 1`).\n\n2. **Iteration 1**:\n   - Calculate `mid = (0 + 1) / 2 = 0`.\n   - Compare `x - A[mid]` (`3 - 1 = 2`) with `A[mid + k] - x` (`5 - 3 = 2`).\n   - Since distances are equal, move `right = mid = 0`.\n\n3. **Final Subarray**:\n   - The loop terminates with `left = 0`.\n   - The closest subarray is `[1, 2, 3, 4]`.\n\n**\uD83D\uDCBB Code**\n\n```cpp []\nvector<int> findClosestElementsmostoptimal(vector<int>& A, int k, int x) {\n    int left = 0, right = A.size() - k;\n    while (left < right) {\n        int mid = (left + right) / 2;\n        if (x - A[mid] > A[mid + k] - x)\n            left = mid + 1;\n        else\n            right = mid;\n    }\n    return vector<int>(A.begin() + left, A.begin() + left + k);\n}\n```\n``` python []\ndef findClosestElements_most_optimal(A, k, x):\n    left, right = 0, len(A) - k\n    while left < right:\n        mid = (left + right) // 2\n        if x - A[mid] > A[mid + k] - x:\n            left = mid + 1\n        else:\n            right = mid\n    return A[left:left + k]\n\n# Example usage:\nA = [1, 2, 3, 4, 5]\nk = 4\nx = 3\nprint(findClosestElements_most_optimal(A, k, x))  # Output: [1, 2, 3, 4]\n\n```\n``` java []\nimport java.util.*;\n\npublic class Main {\n    public static List<Integer> findClosestElements_most_optimal(List<Integer> A, int k, int x) {\n        int left = 0, right = A.size() - k;\n        while (left < right) {\n            int mid = (left + right) / 2;\n            if (x - A.get(mid) > A.get(mid + k) - x) {\n                left = mid + 1;\n            } else {\n                right = mid;\n            }\n        }\n        return A.subList(left, left + k);\n    }\n\n    public static void main(String[] args) {\n        List<Integer> A = Arrays.asList(1, 2, 3, 4, 5);\n        int k = 4;\n        int x = 3;\n        System.out.println(findClosestElements_most_optimal(A, k, x));  // Output: [1, 2, 3, 4]\n    }\n}\n\n```\n**\uD83D\uDCCA Complexity Analysis**\n\n- **Time Complexity**: \n  - The binary search takes `O(log(n - k))`, where `n` is the size of the array.\n  - Extracting the `k` elements takes `O(k)`.\n  - Thus, the total time complexity is `O(log(n - k) + k)`.\n\n- **Space Complexity**: \n  - The space complexity is `O(k)` for storing the result, as no additional space beyond storing the result is needed.\n\n**\u2728 Summary**\n\nThis approach efficiently finds the `k` closest elements to `x` in a sorted array using binary search. By comparing potential subarrays and narrowing down the best starting point, it ensures that the result is accurate and computed with minimal complexity. This method is optimal for handling large arrays where a straightforward comparison-based approach might be too slow.\n
['Array', 'Two Pointers', 'Binary Search', 'Sliding Window', 'Sorting', 'Heap (Priority Queue)', 'C++', 'Java', 'Python3']