Link to the problem:
https://www.hackerrank.com/contests/zenhacks/challenges/find-maximum-index-product
Problem Statement in a nutshell:
Given an array of elements,the problem asks us to find two indices ‘l’ & ‘r’ for every indices ‘I’ such that a[l]>a[i] and a[r]>a[i] such that ‘l’ & ‘r’ are as close to ‘I’ as possible and l<I and r>i. And if no such index is found the value for that index is assumed to be “0” else the value is the product of l and r.
My solution:
First let us see various approaches which will give partial mark before looking the actual solution.
Naïve Approach:
Immediately by looking at the question we can guess the brute force solution. For every index ‘i’ move towards the left end of the array till you find an element which is greater than a[i]. If we have found such index we will break and if no such index exists the value will be “0”. Similarly we will do the same procedure in the right direction also.
Time Complexity: In worst case we might have to traverse the entire array and we have to do it for ‘n’ such positions. Hence the time complexity is O(n^2).
A simple optimization:
https://www.hackerrank.com/contests/zenhacks/challenges/find-maximum-index-product
Problem Statement in a nutshell:
Given an array of elements,the problem asks us to find two indices ‘l’ & ‘r’ for every indices ‘I’ such that a[l]>a[i] and a[r]>a[i] such that ‘l’ & ‘r’ are as close to ‘I’ as possible and l<I and r>i. And if no such index is found the value for that index is assumed to be “0” else the value is the product of l and r.
My solution:
First let us see various approaches which will give partial mark before looking the actual solution.
Naïve Approach:
Immediately by looking at the question we can guess the brute force solution. For every index ‘i’ move towards the left end of the array till you find an element which is greater than a[i]. If we have found such index we will break and if no such index exists the value will be “0”. Similarly we will do the same procedure in the right direction also.
Time Complexity: In worst case we might have to traverse the entire array and we have to do it for ‘n’ such positions. Hence the time complexity is O(n^2).
A simple optimization:
Assume we have calculated the ‘l’ array upto index ‘i-1’ and now we are going to find l[i]. If a[i-1] is greater than a[i], then l[i] is just i-1 else we have to find some other value. For that we will do a simple optimization which is clearly explained in the picture. This algorithm on an average is far better than the previous one but it is not sufficent to get 100 points as in worst case we might scan the entire array
How to get 100 Points:
The technique used is very much similar to the above one, except that we will calculat both l[i] & r[i] in a single scan of the array. The trick is that when we have found an index ‘j’ such that a[j]>a[i] and j<i we can immediately come to a conclusion that r[j]>i. At every step we will update both the arrays l & r. Once we have reached the index n we can find the answer in one single scan. I haven't dealt with few corner cases here and I leave it for the readers to figure it out by themselves!!
Happpppy Coding !!
How to get 100 Points:
The technique used is very much similar to the above one, except that we will calculat both l[i] & r[i] in a single scan of the array. The trick is that when we have found an index ‘j’ such that a[j]>a[i] and j<i we can immediately come to a conclusion that r[j]>i. At every step we will update both the arrays l & r. Once we have reached the index n we can find the answer in one single scan. I haven't dealt with few corner cases here and I leave it for the readers to figure it out by themselves!!
Happpppy Coding !!