Find min(A[L], max(A[L+1], min(A[L+2],...,a[R]))) in range

user_17061998 0
Viewed 167

Give array A consist of N (1 <= N <= 10^5) positive integer less than 10^6. Given Q (1 <= Q <= 10^5) queries, for each query of the form (L, R) (1 <= L <= R <= N), print out:

min(A[L], max(A[L+1], min(A[L+2], ...A[R]))))

Note that we DON'T take the min value of (A[L+2], A[L+3], ..., A[R-1], a[R]). 'Min' and 'max' are interleaved.

  • For example: A[10] = {3, 1, 4, 5, 5, 2, 7, 8, 1, 1} and 1 query (1, 8):
min(A[1], max(A[2], min(A[3], max(A[4], min(A[5], max(A[6], min(A[7], A[8])))))))

= min(3, max(1, min(4, max(5, min(5, max(2, min(7, 8)))))))

= min(3, max(1, min(4, max(5, min(5, max(2, 7))))))

= min(3, max(1, min(4, max(5, min(5, 7)))))

= min(3, max(1, min(4, max(5, 5))))

=min(3, max(1, min(4, 5)))

=min(3, max(1, 4))

=min(3, 4) 

= 3
  • My solution is for each query, consider all A[i] (L <= i <= R) to get the result. But it is not possible because N <= 10^5. Is there any other solution to this problem? Thanks everyone.
math data-structures algorithm
2 Answers

One way to optimize this is to use dynamic programming.

For all R - L + 1 >= 3, note that

Q(L, R) = min(A[L], max(A[L+1], Q(L+2, R))

Furthermore, note that min(a, max(b, c)) = min(a, b) = a if a <= b as max(b, c) >= b >= a. This helps conclude that Q(L, R) = A[L] for all L where A[L] <= A[L+1], regardless of the value of R. You may also choose to use the fact that max(a, min(b, c)) = max(a, b) = a if a >= b to reach a similar conclusion for max(A[L+1], Q(L+2, R)) (and hence Q(L, R)) if A[L] > A[L+1] >= A[L+2].

user_40381910

Suggesting this awk solution, which is easy to convert to your programming language or pseudo code:

Added some comments to explain the script logic.

Essentially scan the array back, flipping/swapping array values by current compare function min/max.

script.awk

function echoArr( title, arr, arrSize) { # echo the current array into a single line
  printf ("%s: ", title);
  for (idx = 1; idx <= arrSize; idx++) printf ("[%d]=%-7d", idx, arr[idx]);
  print "";
}

function swapOnMaxOrMin(arr, idx, compareIndicator) { # swap arr[i] with arr[i-1] following compareIndicator
                                                      # compareIndicator > 0: swap arr[i] with arr[i-1], if arr[i] > arr[i-1]
                                                      # compareIndicator < 0: swap arr[i] with arr[i-1], if arr[i] < arr[i-1]
  if (compareIndicator > 0 ) { # max compare
    if (arr[idx] > arr[idx - 1]) { # swap arr values
      tempInt = arr[idx - 1];
      arr[idx - 1] = arr[idx];
      arr[idx] = tempInt;
    }
  }
  if (compareIndicator < 0 ) { # min compare
    if (arr[idx] < arr[idx - 1]) { # swap arr values
      tempInt = arr[idx - 1];
      arr[idx - 1] = arr[idx];
      arr[idx] = tempInt;
    }
  }
}

END {
  numsArrSise = int($1); # Array size is field #1 `N`
  topNumber = int($2);   # top number in array is field #2  `999999`
  for (i = 1; i <= numsArrSise; i++) numsArr[i] = int(rand() * topNumber) + 1; # popluate array with random numbers
  echoArr("Initial   ", numsArr, numsArrSise); # display the initial array

  queryBottom = int($3); # lower index in query `L`
  queryTop = int($4);    # top index in query  `R`

  if (queryBottom >= queryTop) { # assert `L` < `R`
    printf "rejected: %d >= %d ", queryBottom, queryTop;
    exit;
  }

  if (queryTop > numsArrSise) { # assert `R` < `N`
    printf "rejected: %d > %d ", queryTop, numsArrSise;
    exit;
  }

  if (queryBottom < 1) { # assert 0 < `L`
    printf "rejected: %d > %d ", queryBottom, 1;
    exit;
  }

  compareIndicator=1; # start comparing with `max()`
  for (i = queryTop; i > queryBottom; i--) { # scan down array from `R` ---> `L`
    title = sprintf("%s(%2d,%2d)", compareIndicator > 0 ? "max": "min", i-1, i); # set echo title: max(i-1,i) or min(i-1,i)
    swapOnMaxOrMin(numsArr, i, compareIndicator); # swap values for numsArr[i-1] with numsArr[i] based on compare indicator
    echoArr(title, numsArr, numsArrSise); # echo the current array after the swap
    compareIndicator *= -1; # rotate/flip max() with min()
  }
  printf("arr[%d]=%d\n", i, numsArr[i]); # print final result
}

Running this script:

Where N=10 L=1 R=10

Used max number 52 instead of 999999

$ awk -f script.awk <<< $(echo 10 52 1 10 )
Initial   : [1]=49     [2]=31     [3]=16     [4]=31     [5]=39     [6]=41     [7]=23     [8]=18     [9]=41     [10]=6      
max( 9,10): [1]=49     [2]=31     [3]=16     [4]=31     [5]=39     [6]=41     [7]=23     [8]=18     [9]=41     [10]=6
min( 8, 9): [1]=49     [2]=31     [3]=16     [4]=31     [5]=39     [6]=41     [7]=23     [8]=18     [9]=41     [10]=6
max( 7, 8): [1]=49     [2]=31     [3]=16     [4]=31     [5]=39     [6]=41     [7]=23     [8]=18     [9]=41     [10]=6
min( 6, 7): [1]=49     [2]=31     [3]=16     [4]=31     [5]=39     [6]=23     [7]=41     [8]=18     [9]=41     [10]=6
max( 5, 6): [1]=49     [2]=31     [3]=16     [4]=31     [5]=39     [6]=23     [7]=41     [8]=18     [9]=41     [10]=6      
min( 4, 5): [1]=49     [2]=31     [3]=16     [4]=31     [5]=39     [6]=23     [7]=41     [8]=18     [9]=41     [10]=6
max( 3, 4): [1]=49     [2]=31     [3]=31     [4]=16     [5]=39     [6]=23     [7]=41     [8]=18     [9]=41     [10]=6
min( 2, 3): [1]=49     [2]=31     [3]=31     [4]=16     [5]=39     [6]=23     [7]=41     [8]=18     [9]=41     [10]=6
max( 1, 2): [1]=49     [2]=31     [3]=31     [4]=16     [5]=39     [6]=23     [7]=41     [8]=18     [9]=41     [10]=6
arr[1]=49

Where N=12 L=2 R=8

Used max number 999 instead of 999999

awk -f script.awk <<< $(echo 12 999 2 8 )
Initial   : [1]=924  [2]=594  [3]=307  [4]=579  [5]=740  [6]=787  [7]=436  [8]=332  [9]=779  [10]=101  [11]=785  [12]=835  
max( 7, 8): [1]=924  [2]=594  [3]=307  [4]=579  [5]=740  [6]=787  [7]=436  [8]=332  [9]=779  [10]=101  [11]=785  [12]=835
min( 6, 7): [1]=924  [2]=594  [3]=307  [4]=579  [5]=740  [6]=436  [7]=787  [8]=332  [9]=779  [10]=101  [11]=785  [12]=835
max( 5, 6): [1]=924  [2]=594  [3]=307  [4]=579  [5]=740  [6]=436  [7]=787  [8]=332  [9]=779  [10]=101  [11]=785  [12]=835
min( 4, 5): [1]=924  [2]=594  [3]=307  [4]=579  [5]=740  [6]=436  [7]=787  [8]=332  [9]=779  [10]=101  [11]=785  [12]=835  
max( 3, 4): [1]=924  [2]=594  [3]=579  [4]=307  [5]=740  [6]=436  [7]=787  [8]=332  [9]=779  [10]=101  [11]=785  [12]=835
min( 2, 3): [1]=924  [2]=579  [3]=594  [4]=307  [5]=740  [6]=436  [7]=787  [8]=332  [9]=779  [10]=101  [11]=785  [12]=835
arr[2]=579
user_62661920
Related