Menu
I came across this question on a website. As mentioned there, it was asked in amazon interview. I couldn't figure out a proper solution in given constraint.
Given an array of n integers, find 3 elements such that a[i] < a[j] < a[k] and i < j < k in O(n) time.
522
Solution Approachif (arr[i] > max) -> max3 = max2, max2 = max , max = arr[i]. else if (arr[i] > max2) -> max3 = max2, max2 = arr[i]. else if (arr[i] > max3) -> max3 = arr[i]. At the end of the loop, we will print all three values.
Check if arr[i]+arr[j]==arr[k] or arr[i]+arr[k]==arr[j] or arr[k]+arr[j]==arr[i] If true then increment count. At the end of all loops count will have a total number of triplets that meet the condition. Return the count as result.
Iterate through the array and check whether the current array element is greater than its preceding element. If all the elements are greater than its preceding element return true, else return false. Here is the source code of the Java Program to Check if an Array is Strictly Increasing.
First, iterate through the array and find maximum. Store this as first maximum along with its index. Now traverse the whole array finding the second max, excluding the maximum element. Finally traverse the array the third time and find the third largest element i.e., excluding the maximum and second maximum.
So here is how you can solve the problem. You need to iterate over the array three times. On the first iteration mark all the values that have an element greater than them on the right and on the second iteration mark all the elements smaller than them on their left. Now your answer would be with an element that has both:
int greater_on_right[SIZE]; int smaller_on_left[SIZE]; memset(greater_on_rigth, -1, sizeof(greater_on_right)); memset(smaller_on_left, -1, sizeof(greater_on_right)); int n; // number of elements; int a[n]; // actual elements; int greatest_value_so_far = a[n- 1]; int greatest_index = n- 1; for (int i = n -2; i >= 0; --i) { if (greatest_value_so_far > a[i]) { greater_on_right[i] = greatest_index; } else { greatest_value_so_far = a[i]; greatest_index = i; } } // Do the same on the left with smaller values for (int i =0;i<n;++i) { if (greater_on_right[i] != -1 && smaller_on_left[i] != -1) { cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_right[i] << endl; } } This solution iterates 3 times over the whole array and is therefore linear. I have not provided the whole solution so that you can train yourself on the left to see if you get my idea. I am sorry not to give just some tips but I couldn't figure out how to give a tip without showing the actual solution.
Hope this solves your problem.
131
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
