This was one of the simple problems of this month. A lot of you were able to solve it easily. The constraints of the problem were such that only O(n) solution could pass. The problem could be stated simply as: Find 2 numbers ai and aj such that aj-ai is maximum. (1 <= i < j <= N) A couple of approaches to this problem: Approach 1: Store the numbers in an array a. Take 2 additional arrays b & c. b[i]=maximum over all ax (for all x such that i<=x<=n) c[i]=minimum over all ax (for all x such that 1<=x<=i) Both these arrays can be computed in O(n) time and space. Clearly, answer will be max(b[i]-c[i]) for all i. This can be found in O(n) too. Approach 2: Take a variable âminmâ which denotes the minimum value encountered so far. Let âansâ denote the maximum difference achieved so far. Read the numbers one by one. Let current value be cur. ans=max(ans,cur-minm) minm=min(minm,cur); Finally, the answer would be in âansâ.
how can the given two arrays can be computed in O(n) time complexity will u please explain it a bit more i am not in hurry to look into the solutionâŚ
Approach 1: Store the numbers in an array a. Take 2 additional arrays b & c. b[i]=maximum over all ax (for all x such that i<=x<=n) c[i]=minimum over all ax (for all x such that 1<=x<=i)
What does this paragraph mean?
@shubham99 Reduce the complexity of your solution. It is n^2.
As it is pointed above âThe constraints of the problem were such that only O(n) solution could pass.â
For a nested loop, the time complexity is n^2 as there are n^2 iterations.
For, say 3 independent loops, the number of iterations are 3n. We ignore constants when calculating time complexity. Hence independent loops will have linear or O(n) time complexity.