<p>Given a <strong>sorted</strong> integer array <code>arr</code>, two integers <code>k</code> and <code>x</code>, return the <code>k</code> closest integers to <code>x</code> in the array. The result should also be sorted in ascending order.</p>

<p>An integer <code>a</code> is closer to <code>x</code> than an integer <code>b</code> if:</p>

<ul>
	<li><code>|a - x| &lt; |b - x|</code>, or</li>
	<li><code>|a - x| == |b - x|</code> and <code>a &lt; b</code></li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> arr = [1,2,3,4,5], k = 4, x = 3
<strong>Output:</strong> [1,2,3,4]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> arr = [1,2,3,4,5], k = 4, x = -1
<strong>Output:</strong> [1,2,3,4]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= arr.length</code></li>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>4</sup></code></li>
	<li><code>arr</code> is sorted in <strong>ascending</strong> order.</li>
	<li><code>-10<sup>4</sup> &lt;= arr[i], x &lt;= 10<sup>4</sup></code></li>
</ul>

// class Solution {
// public:
//     vector<int> findClosestElements(vector<int>& arr, int k, int x) {
//         int n=arr.size();
//         vector<int>ans(k);
//         if(x<arr[0]){
//             for(int i=0;i<k;i++){
//                 ans[i]=arr[i];
//             }
//             return ans;

//         }
//         if(x>arr[n-1]){
//             int i=n-1;
//             int j=k-1;
//             while(j>=0){
//                 ans[j]=ans[i];
//                 j--;
//                 i--;
//             }
//             return ans;

//         }
//         int lo=0;
//         int hi=n-1;
//         bool flag=false; //if x is present in arr or not
//         int t=0;
//         int mid=-1; // representing index of ans
//         //binary search
//         while(lo<=hi){
//             mid=lo+(hi-lo)/2;
//             if(arr[mid]==x){
//                 flag=true;
//                 ans[t]=arr[mid];
//                 t++;
//                 break;
//             }
//             else if (arr[mid]>x) hi=mid-1;
//             else lo=mid+1;
//         }
//         int lb=hi;
//         int ub=lo;
//         if(flag==true){
//             lb=mid-1;
//             ub=mid+1;
//         }
//         while(t<k && lb>=0 &&ub<=n-1){
//             int d1=abs(x-arr[lb]);
//             int d2=abs(x-arr[ub]);
//             if(d1<=d2){
//                 ans[t]=arr[lb];
//                 lb--;
//             }
//             else{
//                 ans[t]=arr[ub];
//                 ub++;
//             }
//             t++;

//         }
//         if(lb<0){
//             while(t<k){
//                 ans[t]=arr[ub];
//                 ub++;
//                 t++;
//             }
//         }
//         if(ub>n-1){
//             while(t<k){
//                 ans[t]=arr[lb];
//                 lb--;
//                 t++;
//             }
//         }
//         sort(ans.begin(),ans.end());
//         return ans;
        
//     }
// };
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n = arr.size();
        vector<int> ans;  // Initialize ans as an empty vector
        
        // Handle cases where x is smaller than the smallest element
        if (x < arr[0]) {
            for (int i = 0; i < k; i++) {
                ans.push_back(arr[i]);  // Use push_back to avoid out-of-bounds access
            }
            return ans;
        }
        
        // Handle cases where x is larger than the largest element
        if (x > arr[n - 1]) {
            for (int i = n - k; i < n; i++) {
                ans.push_back(arr[i]);  // Use push_back for the last k elements
            }
            return ans;
        }

        // Binary search to find the closest element or insertion point
        int lo = 0, hi = n - 1;
        bool flag = false;  // Check if x is present in arr
        int mid = -1;       // Index of x if it's found

        // Binary search
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (arr[mid] == x) {
                flag = true;
                ans.push_back(arr[mid]);  // Use push_back instead of direct index access
                break;
            } else if (arr[mid] > x) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        int lb = hi;  // Left boundary
        int ub = lo;  // Right boundary
        int t = flag ? 1 : 0;  // If x was added, initialize t to 1

        // Adjust lb and ub if x was found
        if (flag) {
            lb = mid - 1;
            ub = mid + 1;
        }

        // Finding k closest elements
        while (t < k && lb >= 0 && ub < n) {
            int d1 = abs(x - arr[lb]);
            int d2 = abs(x - arr[ub]);

            if (d1 <= d2) {
                ans.push_back(arr[lb--]);  // Use push_back to avoid index access
            } else {
                ans.push_back(arr[ub++]);  // Use push_back
            }
            t++;
        }

        // If we run out of elements on the left side
        while (t < k && ub < n) {
            ans.push_back(arr[ub++]);  // Use push_back
            t++;
        }

        // If we run out of elements on the right side
        while (t < k && lb >= 0) {
            ans.push_back(arr[lb--]);  // Use push_back
            t++;
        }

        // Sorting the result to maintain ascending order
        sort(ans.begin(), ans.end());

        return ans;
    }
};

35400