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];
           arr[i] = -1;
   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)
  • $\begingroup$ I don't really understand the original question. What is the input, and what is the desired output? Are there any examples provided? $\endgroup$ Feb 26, 2021 at 14:52
  • $\begingroup$ @YuvalFilmus I have edited my question (added input, output and explanation). $\endgroup$
    – salazarin
    Feb 26, 2021 at 16:19
  • $\begingroup$ Can you tell us where you encountered this task? Can you provide attribution or a link to the original source? What is meant by "the current index"? I find it hard to reconcile that with "For each element". Please explain what is meant by "the current index". $\endgroup$
    – D.W.
    Feb 26, 2021 at 20:39
  • $\begingroup$ cs.stackexchange.com/q/192/755, cs.stackexchange.com/q/23593/755 $\endgroup$
    – D.W.
    Feb 26, 2021 at 20:40
  • $\begingroup$ @D.W. This is the link to the question practice.geeksforgeeks.org/problems/… ! The question is asking to update/replace the value at current index with the value at it's right adjacent index. (Condition- value at right adjacent index (at jth position) index is smaller than the value at the current index (ith position)). $\endgroup$
    – salazarin
    Feb 26, 2021 at 20:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.