https://practice.geeksforgeeks.org/problems/three-great-candidates/0#ExpectOP.
can u tell me how to approach this problem.
and in java if we have to create an array of size greater than 10^9 how we will do.
Array concept problem
@Sumant123
Basically the problem is finding out a sequence of length 3. So,
A naive approach can be O(n ^ 3) :-
using three nested loops and calculate the product and update the maximum.
Sorting approach O(nlogn):-
Sort the array first now maximum product can be in two cases:-
- The last three elements can form the maximum product.
- First two elements and last elements.(first two negative number product will make positive).
O(n) approach:-
- This approach can be intuitively derived from sorting approach.
- Find first largest, second largest and third largest element in o(n) time. (first point in above approach)
- Find first smallest and second smallest in O(n) time. (second point in above approach)
The problem is not demanding array of size that big so don’t think of those cases until asked, we will sort it out if we get the constraints, there are other data structures which we can use at that time but that depends on problem. Array of that big size will take 4 gb of memory thats why it is not allowed.
If you have any doubts regarding approach, feel free to ask, else resolve the doubt and rate full.