Gary and multiplication — Asked in Intuit and American Express Interviews

Problem Statement :

Gary has recently learned about priority queues and is quite excited about them. He has asked his teacher for an interesting problem. So, his teacher came up with a simple problem.

The problem is that he now has an integer array ‘ARR’. For every index i, he wants to find the product of the largest, second largest and the third largest integer in the range [0, i] given that array has 0 based indexing.

You have to return the list as required.

Sample Input:

42 3 1 4

Sample Output:

-1 -1 6 24

Explanation of given Test Cases :

-1 (no second largest as well as third largest element is present)
-1 (no third largest element is present)
6 (3 * 2 * 1)
24 (4 * 3 * 2)

Approach :

Priority Queue

  1. The idea is to work with the max priority queue.
  2. Insert the elements of array ‘ARR’ one by one.
  3. Once you add the element, extract 3 elements from the max priority queue. They will, of course, be largest (the one extracted the first time), second largest (the one extracted the second time) and third largest (the one extracted the third time).
  4. It should be noted that while executing point 3, one should take care of the time when the size of the priority queue will be less than 2.
  5. Now, all you need to do is find the product of the three numbers and print the answer.

But this would give Space complexity of O(N). So we will modify a bit.

Using O(1) Space

  1. The idea is to use 3 elements. One for largest, one for second largest and one for third largest.
  2. Now, all we need to do is iterate the whole array while maintaining the appropriate values in the variables and keep on printing the answer.

Time complexity: O(N)
Space complexity: O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

The sum of length of two trains is 864 m. the ratio between the speed

5 Misconceptions About Kanban

Designing Resilient Microservices — Part 2

AWS Docker Gitlab Serverless - The easy way.

Photo form: https://www.freeimages.com/es/photo/communicate-1-1241953

First Steps to the OpenCV-Python

How do recruitment platforms solve the issues of today’s job market?

Weekly newsletter of Eduard Stefanescu — 14 Mar 2021

5 Habits of Successful Software Developers

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Class Quiz

Leetcode Q313. Super Ugly Number (Q266)

LeetCode 1721: Swapping Nodes in a Linked List

MCLT — More Code Less Talk

The pandemic of Data Structures and Algorithms Courses