Find the Maximum Difference of Indices

Revision en34, by harsha314, 2021-08-08 14:28:56

Given an array $$$A$$$ of $$$N$$$ integers . Find the maximum of value of $$$i\ -\ j$$$ such that : $$$\newline$$$ $$$1)\ j\ \le\ i \newline$$$ $$$2)\ A[j]\ \le\ A[i] \newline$$$

Note : $$$i$$$ and $$$j$$$ are 0-based indices

Constraints :
$$$ N \le 10^6\ ;\ A[i]\ \le\ 10^9\ for\ 0\ \le i\ \le\ N-1\newline $$$

Ex :

  • $$$A\ =\ [1,2,3,4,5]$$$
    $$$j\ =\ 0\ ,\ i\ =\ 4$$$ gives maximum difference of 4 satisfying the given conditions

  • $$$A\ =\ [8,4,8,7,6,6,3]$$$
    $$$j\ =\ 1\ ,\ i\ =\ 5$$$ gives maximum difference of 4 satisfying the given conditions
    • Note : This question was asked in an on-campus coding exam & it was completed

      Forgive me for the English & formatting.

Tags #array, #maximise

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en35 English harsha314 2021-08-08 14:29:14 0 (published)
en34 English harsha314 2021-08-08 14:28:56 7
en33 English harsha314 2021-08-08 14:28:28 134 (saved to drafts)
en32 English harsha314 2021-08-08 14:20:24 0 (published)
en31 English harsha314 2021-08-08 14:19:00 4 Tiny change: 'N \le 10^6 , A[i]\ \le' -> 'N \le 10^6\ ;\ A[i]\ \le'
en30 English harsha314 2021-08-08 14:18:36 9 Tiny change: 'traints : $ N \le 10' -> 'traints : \n<br/>\n$ N \le 10'
en29 English harsha314 2021-08-08 14:18:17 4 Tiny change: 'n\nNote : i and j are 0-bas' -> 'n\nNote : $i$ and $j$ are 0-bas'
en28 English harsha314 2021-08-08 14:17:27 8
en27 English harsha314 2021-08-08 14:16:44 9
en26 English harsha314 2021-08-08 14:16:07 9
en25 English harsha314 2021-08-08 14:15:35 16
en24 English harsha314 2021-08-08 14:14:44 13
en23 English harsha314 2021-08-08 14:14:14 13 Tiny change: 'nditions\n A =' -> 'nditions\n</li>\n<li>\n A ='
en22 English harsha314 2021-08-08 14:13:48 42
en21 English harsha314 2021-08-08 14:13:04 56
en20 English harsha314 2021-08-08 14:11:45 11
en19 English harsha314 2021-08-08 14:10:38 4 Tiny change: 'le 10^6 , $\n$A[i]\ \le\' -> 'le 10^6 , A[i]\ \le\'
en18 English harsha314 2021-08-08 14:10:15 8 Tiny change: '\ \le\ N-1 $\nEx : A' -> '\ \le\ N-1\newline $\nEx : A'
en17 English harsha314 2021-08-08 14:09:43 33
en16 English harsha314 2021-08-08 14:08:28 17
en15 English harsha314 2021-08-08 14:06:48 14
en14 English harsha314 2021-08-08 14:06:26 18
en13 English harsha314 2021-08-08 14:04:41 4
en12 English harsha314 2021-08-08 14:04:17 10
en11 English harsha314 2021-08-08 14:02:02 4 Tiny change: 'aints : \nN <= 10^6 , \nA[i] <= 10' -> 'aints : \n- N <= 10^6 , \n- A[i] <= 10'
en10 English harsha314 2021-08-08 14:01:08 9
en9 English harsha314 2021-08-08 13:59:28 6
en8 English harsha314 2021-08-08 13:58:29 12
en7 English harsha314 2021-08-08 13:57:58 9 Tiny change: 'uch that :\n1) $j\ <' -> 'uch that : \newline\n1) $j\ <'
en6 English harsha314 2021-08-08 13:57:32 9 Tiny change: ' $j\ <\ i\\ $\n2) $A[j' -> ' $j\ <\ i\newline$\n2) $A[j'
en5 English harsha314 2021-08-08 13:57:08 1 Tiny change: '$j\ <\ i\\$\n2) $A[j' -> '$j\ <\ i\\ $\n2) $A[j'
en4 English harsha314 2021-08-08 13:56:44 2 Tiny change: ') $j\ <\ i$\n2) $A[j' -> ') $j\ <\ i\\$\n2) $A[j'
en3 English harsha314 2021-08-08 13:56:08 8
en2 English harsha314 2021-08-08 13:55:28 12 Tiny change: ' value of i &mdash; j such that' -> ' value of $i\ -\ j$ such that'
en1 English harsha314 2021-08-08 13:54:31 465 Initial revision (saved to drafts)