Implement Immediate Smaller Element problem using Stack

Question

Immediate Smaller Element Problem:

Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next immediate position) of the array is smaller. If next element is smaller, update the current index to that element. If not, then update it to –1.

Input: arr[] = {4, 2, 1, 5, 3}

Output: arr[] = {2, 1, -1, 3, -1}

Explanation: Next to 4 is 2 which is smaller, so we replace 4 with 2. Next of 2 is 1 which is smaller, so we replace 2 with 1. Next of 1 is 5 which is greater, so replace 1 with -1. Next of 5 is 3 which is smaller, so replace 5 with 3. The output for the last element is always going to be -1 because there is no element on right.

This is my solution:

void immediateSmaller(int arr[], int n) {
    int i = 0, j = i + 1;
    while(i < n - 1) {
        if(arr[i] > arr[j]) 
           arr[i] = arr[j];
        else 
           arr[i] = -1;
       i++;
       j++;
   }
   arr[j - 1] = -1;
}

My queries are:

• Is the time complexity of my solution $O(n)$ or $O(n^2)$? I think it should be $O(n)$ since there is only one loop here.
• How can this question be implemented using a Stack data structure? (My solution works fine but recommended approach is to use a Stack)