<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 POP_PUSH
{
    public:
    int k;
    int* A;
    int back;
    int front;
    int sz;
    POP_PUSH(int m) : k(m), back(-1), front(m), sz(0)
    {
        A = new int[m] ;
    }

    void push_front(int r)
    {
        A[--front] = r;
        sz++;
    }

    void push_back(int r)
    {
        A[++back] = r;
        sz++;
    }
};

class Solution {
    #define min(a, b) (a<b)?a:b
public:
    vector<int> findClosestElements(vector<int>& A, int k, int x)
    {
        int n = A.size() ;
        vector<int> sol(k, 0) ;
        int l = 0;
        while(l<n && A[l]<x) { l++; }
        POP_PUSH arr(k) ;
        int ptr1 = l-1, ptr2 = l;
        while(arr.sz<k)
        {
            if (ptr1>=0 && ptr2<n)
            {
                if (x-A[ptr1]<A[ptr2]-x)
                {
                    arr.push_front(A[ptr1--]) ;
                }
                else if(x-A[ptr1]>A[ptr2]-x)
                {
                    arr.push_back(A[ptr2++]) ;
                }
                else
                {
                    arr.push_front(A[ptr1--]);
                }
            }
            else if(ptr1<0)
            {
                arr.push_back(A[ptr2++]) ;
            }
            else
            {
                arr.push_front(A[ptr1--]) ;
            }
        }
        for(int i = arr.front; i<arr.front+k; i++)
        {
            sol[i-arr.front] = arr.A[i%k] ;
        }

        return sol;
    }
};

// class Solution {
// public:
//     vector<int> findClosestElements(vector<int>& A, int k, int x) {
//         int n = A.size();
//         int l = 0, r = n - 1;
        
//         // Find the closest position to x
//         while (r - l >= k) {
//             if (x - A[l] > A[r] - x) {
//                 l++;
//             } else {
//                 r--;
//             }
//         }
        
//         // Collect the k closest elements
//         vector<int> result(A.begin() + l, A.begin() + r + 1);
//         return result;
//     }
// };

34300