Forem: late_riser

Leetcode 713. Subarray Product Less Than K

late_riser — Tue, 09 Aug 2022 21:26:57 +0000

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example 1

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2

Input: nums = [1,2,3], k = 0
Output: 0

Constraints

1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106

Editorial

The simplest way to think of this problem is taking cumulative product from an index up to the end of the array. Then check if any of those products < k or not. We will have to do this for each index. Then, for any subarray product < k, we can count the number of subarrays and find the result by adding up those counts.

But this approach will cost us O(N2) [O N square] runtime which is not efficient and we don't want that! So, let's not waste time on it. The better approach to solve this problem is to .... read more

Editorial source: foolishhungry blog

Search in Rotated Sorted Array (Leetcode 33)

late_riser — Sat, 06 Aug 2022 03:04:00 +0000

Problem
There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(logn) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Source: Leetcode

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

How to solve this interesting problem?

If a sorted array is not rotated, it is easy to find a target value using Binary Search algorithm. Because, we know the target value will be somewhere between the first and the last element of the array. But if we rotate the array, the array no longer remains sorted, right?

Leetcode 523. Continuous Subarray Sum

late_riser — Tue, 26 Jul 2022 17:56:37 +0000

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

Constraints:

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1

Solution: Here is the link of our blog to the solution of this problem:
continuous subarray sum - FoolishHungry Blog

Leetcode-42: Trapping Rain Water

late_riser — Thu, 14 Oct 2021 18:13:08 +0000

This article is taken from FOOLISH HUNGRY blog.

The Problem
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
Source: Leetcode

ALERT, ALERT, ALERT !!!

If you have come to see the solution before trying to solve it yourself, this really won’t help you, promise! If that is the case, we will recommend, please go back and first try it yourself. If you can’t solve it after (at least)an hour of thinking and trying, please come back! 🙂 You can solve it here

Solution

Consider we have only three elevations named A, B and C with heights [10, 5, 20]. If we continue to pour water on elevation 5, it will remain on top of 5 until it reaches 10. Anything above 10 will be drained away as show below.

So, for B, the effective height of water is the minimum height of all the maximum heights that belong to both sides of B.

In other words, for any elevation,

effective height for B = min ( max(all heights to the left of B), max(all heights to the right of B))

Before jumping into the code, let’s do a little simulation of the idea of effective height and trapped rain water calculation.

Consider we have 5 elevation points with heights [10, 0, 5, 0, 20] as below.

(Sorry for the drawing mistake, height of E doesn’t look proportionate to A or C 😛 That won’t hurt understanding the solution though )

Let’s start with elevation point A. There is no point left to it, so, the max height to A is the height of itself, 10. There are 4 points right to A with heights [0, 5, 0, 20]. The max is 20. So, the minimum between left max and right max is 10. So, the effective height is 10 – 10 = 0. That means, elevation point A cannot trap any water.

In the same way, max height to the left of B is 10 and to the right of B is 20. Effective height is min(10, 20) = 10 and B can trap 10 – 0 = 10 units of water.

Next three images show with calculation how much water C, D and E can trap.

So, the total unit of water trapped will be 0 + 10 + 5 + 10 + 0 = 25.

The Algorithm

To find the maximum height to the left and right of an elevation point, we can loop from that point and go to left once and go to right again. So, this will cause a runtime complexity of O(N2). However, we will get O(1) space complexity since we are not using any extra spaces.

Runtime complexity can easily be improved to O(N) if we apply simple Dynamic Programming and store the max value so far from the beginning of the array in another array called left. Also, we can store the same starting from the end of the array in another array called right. Then each time we want to know the max values of left and right of an elevation point, we will simply check the left and right array.

So, formally, the algorithm is:

Start from i = 0 to end and store max value in left[ ] array. Do Something like left [i] = max(left[i – 1], height [i] )
Start from i = end to 0 and store max value in left[ ] array. Do Something like right [i] = max(right[i + 1], height [i] )
Now, loop through the height array and take effective height as, effective_height = min (left[i], right[I]). Add trapped water unit.

Code

int trap(vector<int>& height) {
        int N = height.size();

        vector<int> left(N, 0);
        vector<int> right(N, 0);

        left[0] = height[0];
        right[N - 1] = height[N - 1];

        for(int i = 1; i < N; i++){
            left[i] = max(left[i - 1], height[i]);
            right[N - i - 1] = max(height[N - i - 1], right[N - i]);
        }

        int ans = 0;

        for(int i = 0; i < N; i++){
            ans += min(left[i], right[i]) - height[i];
        }

        return ans;
    }

Happy Coding!! :D

This article is taken from FOOLISH HUNGRY blog.

30-Day LeetCoding Challenge (Day-1)

late_riser — Thu, 02 Apr 2020 23:22:41 +0000

Background: We all are home for the current pandemic situation. Leetcode has taken this opportunity to throw a challenge for the users (which is positive, I think).
The challenge is titled 30-Day LeetCoding Challenge. I have started it since yesterday and wish to complete it and write blog post for each problem I solve in a day. This is just to keep myself motivated to stay at home and give something back to the community. As a disclaimer, I have taken problem statements and examples from leetcode. Without any more introduction, I will jump into the problem, how I solved it and link to my code. If you find this helpful, give me a poke!

Problem Title: Single Number

Description: Given a non-empty array of integers, every element appears twice except for one. Find that single one. Your algorithm should have a linear run time complexity i.e. O(n). Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1 (because 1 the only number that is appearing once)

Example 2:

Input: [4,1,2,1,2]
Output: 4 (because 1 the only number that is appearing once)

Solution: I solved this problem using bitwise XOR. The idea is, when you XOR a number with itself, you will get 0. For example, 2441139 ⊗ XOR 2441139 = 0.
Now, say, we have 5 numbers like 3, 4, 9, 3, 9. If we XOR these numbers from begin to end, we will end up XORing 3 twice and 9 twice. Both of them will make the result 0 and 4 will remain intact since any number XOR with 0 ends up to that number. (If you don’t get the idea still, I would suggest you to do the calculations on paper, you should get it for sure!)

Code: Here is my C++ code for it.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int sum = 0;
        for(auto x: nums)
            sum ^= x;
        return sum;

    }
};

If you want to learn more about bitwise operation, this link is a good resource in my opinion.

If you find this helpful or want me to improve my explanation(I think that’s more probable) or want to shout out of anger because of my crappy writing, you can post your comments :).

Stay safe at home! Happy Coding! :)

Follow me on twitter.