Leetcode Solutions #3

1. Top K Frequent Elements

The Problem

First read the description of problem:

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Question is leetcode rating medium but is pretty basic when it comes to implementation.

Refer to the examples below

Approach

Approach is also very basic just like the question:

1. Use map to count the frequency of the elements.

2. Make a key value pair of elements.

3. Return the elements according to the question.

Solution

In the solution we have done the following things,

1. Use an unordered map to count and store frequency of each number.

2. Initialise a vector named bucket with n+1 empty vector. This will group elements with their frequency.

3. Iterate over the map and extract elements and their frequency.

4. Add elements to this bucket corresponding to its frequency. This groups elements by their frequency.

5. Declare a vector result to store final list.

6. Iterates backward to process bucket with higher frequency first.

7. Check for elements in bucket and iterate over each element in bucket.

8. Add current element in result vector and decrease remaining element.

9. Return result.

2. Product of Array Except Self

The Problem

Firstly read the description of problem:

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Question is pretty understandable from its statement only, we have to multiply the elements of the array except the element itself.
The only catch is we have to do this without doing division and in O(n) time complexity.

Here is the example for better understanding,

Approach

Approach is pretty basic here also we just have to make two passes over the array,

1. Left Pass: In first pass, it multiplies each element by product of all elements to the left of each index.

2. Right Pass: In second pass, it multiplies each element by product of all elements to right of the index.

Solution

In this solution we have,

1. Creates a vector result of size n to store final product.

2. Initialises first element of result to 1, because there are no elements to left of first element.

3. Start iterating through nums array.

4. For each index is this calculates the product of all elements to left of i and stores it in result[i] is product of result[i-1] and nums[i-1].

5. Initialise a variable right_product to store product of elements to right of each index. Set it to 1 because there are no elements to right of last element.

6. This loop iterates through nums in reverse order.

7. At each index i, it multiplies the current value of result[i] by right_product.

8. Update right_product by multiplying it with the current elements nums[i]. This allows right_product to hold the product of all elements to right of next elements.

9. Return result.

I hope the solutions I have provided are understandable and explanations are easy to understand.

Thank You

You can connect with me on Linkedin