In this tutorial, I am going to discuss a very interesting problem Product of array except self or product of every integer except the integer at that index.
Given an array of N integers where N > 1. Write a code to print the result/output such that result[i] is equal to the product of all the elements of an array except self (result[i]).
For example –
Input: {4, 2, 1, 7}
Output: {14, 28, 56, 8}
NOTE: We have to solve this problem without division and in linear time O(n).
Find top k frequent elements in an array of integers. Let’s first understand the problem statement and the we will solve this problem using multiple approaches.
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: arr = {3, 4, 4, 4, 7, 7}, k = 2
Output: {4, 7}
Two most frequent elements are 4 and 7.
Example 2:
Input: arr = {3}, k = 1
Output: {3}
NOTE:
* k is always valid, 1 ≤ k ≤ number of unique elements.
* The time complexity must be better than O(nlogn), where n is the array’s size.
* It’s guaranteed that the answer is unique, in other words, the set of the top k frequent elements is unique.
* Answer can be returned in any order.
Maximum consecutive ones III. Find maximum consecutive ones in an array of 0s and 1s, If k flip is allowed.
Given an array which only consists of 0s and 1s. Write a code to find the maximum number of consecutive 1s in an array, if we can flip k zeros.
For example:
Input – {1, 1, 0, 0, 0, 1, 1, 1, 1, 1}, k = 2 (We can flip two zeros)
Output: 7
Explanation:
In this example, If we can flip at most k (which is 2) zero. By flipping the zeros, here we can form following subarrays.
{1, 1, 1, 1} -> From index 0 to 3 (zero is present at index 2 and 3)
One subarray is from index 1 to 3 -> {1, 1, 1}
Another subarray is from index 2 to 3 (As both the element at this index is zero) -> {1, 1}
From index 3 to 9 -> {1, 1, 1, 1, 1, 1, 1}
Out of these, the maximum number of consecutive 1s in an array is 7 {1, 1, 1, 1, 1, 1, 1}.