EDITORIALIST: Harshit kumar
PREREQUISITES: Basic Arithmetic
PROBLEM LINK: ZIO 2011 Problem 3
PROBLEM IN SHORT:
Given an array of numbers, find pair of numbers such that there is no number between them that is strictly taller than either A or B.
OR
Find pair of numbers such that minimum of both numbers is greater than or equal to maximum of the numbers between them.
SOLUTION:
Observation 1: Every adjacent number will satisfy the above criteria because there is no number in between.
Observation 2: In an array if there is a number A and B where B is the first number which is right of A and satisfy the criteria given in question (min(A,B)>= max(all the numbers in between)) then A can only make valid pair with the numbers which is right of B if they are greater than B
Ex. 160 145 73 153 170
(160,145) is a valid pair
(160,73) is not a valid pair because of 145 but (160,153) is a valid pair.
So, as you can see the only valid candidate is the one which is greater than its previous valid number.
Observation 1 & 2: As you can see from observation 1 that the first valid pair for a number will be with its adjacent number and from observation 2 that every number who want to make valid pair should be greater than its previous valid number.
So, the only number which can make valid pair with a specific number are the numbers which comes in Increasing subsequence(any number which is greater than the last number of current sequence should be taken in the sequence) starting from the adjacent number.
Ex. 160 145 73 153 173 180
For 160 Increasing subsequence starting from its adjacent number 145 is (145,153,173,180).
So, these are the only number with which 160 can make a valid pair but we have to check one more condition which we will see in next observation.
Observation 3: In the increasing subsequence a number A can only make valid pair till the first number whose is greater than A because as for 2nd and rest f-greater number 1st greater number will create a problem as it is greater than A.
Ex. 160 145 73 153 173 180
For 160 increasing subsequence starting from its adjacent number 145 is (145,153,173,180) but 160 will make valid pair with only (145,153,173) because for 180 min(160,180)=160 is not greater than max(145,153,173,73)=173.
So, for every number we just need to find increasing subsequence starting from its adjacent number till we get the first greater number.
Example (a): 168, 92, 120, 147, 73, 160, 156, 108, 145, 157, 71, 71, 109, 157, 152, 214, 191, 78, 154, 186
So, for every element count the numbers that comes in Increasing subsequence starting from its adjacent number till the first greater number.
160 → 92,120,147,160,214 (5 valid pairs)
92 → 120 (1 valid pairs)
120 → 147 (1 valid pairs)
147 → 73,160 (2 valid pairs)
73 → 160 (1 valid pairs)
160 → 156,157,157,214 (4 valid pairs)
156 → 108,145,157 (3 valid pairs)
108 → 145 (1 valid pairs)
145 → 157 (1 valid pairs)
157 → 71,71,109,157,214 (5 valid pairs)
71 → 71,109 (2 valid pairs)
71 → 109 (1 valid pairs)
109 → 157 (1 valid pairs)
157 → 152,214 (2 valid pairs)
152 → 214 (1 valid pairs)
214 → 191 (1 valid pairs)
191 → 78,157,186 (3 valid pairs)
78 → 154 (1 valid pairs)
154 → 186 (1 valid pairs)
186 → (0 valid pairs)
Total = 5+1+1+2+1+4+3+1+1+5+2+1+1+2+1+1+3+1+1+0 = 37
Answer = 37
Example(b): 230, 142, 176, 225, 111, 163, 175, 241, 72, 76, 99, 145, 146, 82, 153, 118, 158, 239, 86, 246, 156, 98, 154, 83, 205
230 → 142, 176, 225, 241 (4 valid pairs)
142 → 176 (1 valid pairs)
176 → 225 (1 valid pairs)
225 → 111, 163, 175, 241 (4 valid pairs)
111 → 163 (1 valid pairs)
163 → 175 (1 valid pairs)
175 → 241 (1 valid pairs)
241 → 72, 76, 99, 145, 146, 153, 158, 239, 246 (9 valid pairs)
72 → 76 (1 valid pairs)
76 → 99 (1 valid pairs)
99 → 145 (1 valid pairs)
145 → 146 (1 valid pairs)
146 → 82, 153 (2 valid pairs)
82 → 153 (1 valid pairs)
153 → 118, 158 (2 valid pairs)
118 → 158 (1 valid pairs)
158 → 239 (1 valid pairs)
239 → 86, 246 (2 valid pairs)
86 → 246 (1 valid pairs)
246 → 156, 205 (2 valid pairs)
156 → 98, 154, 205 (3 valid pairs)
98 → 154 (1 valid pairs)
154 → 83, 205 (2 valid pairs)
83 → 20, (1 valid pairs)
Total = 4+1+1+4+1+1+1+9+1+1+1+1+2+1+2+1+1+2+1+2+3+1+2+1 = 45
Answer = 45
Example ( c ): 196, 98, 134, 169, 73, 185, 289, 168, 262, 291, 72, 71, 120, 181, 122, 162, 147, 75, 124, 144, 106, 100, 224, 139, 229, 134, 87, 156, 251, 150
196 → 98, 134, 169, 185, 289 (5 valid pairs)
98 → 134 (1 valid pairs)
134 → 169 (1 valid pairs)
169 → 73, 185 (2 valid pairs)
73 → 185 (1 valid pairs)
185 → 289 (1 valid pairs)
289 → 168, 262, 291 (3 valid pairs)
168 → 262 (1 valid pairs)
262 → 291 (1 valid pairs)
291 → 72, 120, 181, 224, 229, 251 (6 valid pairs)
72 → 71, 120 (2 valid pairs)
71 → 120 (1 valid pairs)
120 → 181 (1 valid pairs)
181 → 122, 162, 224 (3 valid pairs)
122 → 162 (1 valid pairs)
162 → 147, 224 (2 valid pairs)
147 → 75, 124, 144, 224 (4 valid pairs)
75 → 124 (1 valid pairs)
124 → 144 (1 valid pairs)
144 → 106, 224 (2 valid pairs)
106 → 100, 224 (2 valid pairs)
100 → 224 (1 valid pairs)
224 → 139, 229 (2 valid pairs)
139 → 229 (1 valid pairs)
229 → 134, 156, 251 (3 valid pairs)
134 → 87, 156 (2 valid pairs)
87 → 156 (1 valid pairs)
156 → 251 (1 valid pairs)
251 → 150 (1 valid pairs)
Total=5+1+1+2+1+1+3+1+1+6+2+1+1+3+1+2+4+1+1+2+2+1+2+1+3+2+1+1+1 = 54
Answer = 54.
Note (For programmers): The time complexity of this algorithm is O(n^2), you can also this problem in O(n) by precomputing an array which will contains 1st greater number in right and left for every number with the help of stack but you have to deal with lots of corner cases which will hard to cover by just visualising. So, for ZIO purpose this algorithm works well and it takes less time as well.