Showing posts with label Array. Show all posts
Showing posts with label Array. Show all posts

Wednesday, January 26, 2022

First Missing Positive Number

 41. First Missing Positive - Leetcode, Hard


সহজ প্রবলেম ডেসক্রিপশন, 

N সাইজের একটা Array দেয়া আছে, সব গুলাই Integer এবং Positive/Negative সব ধরনের নাম্বার ই থাকতে পারে।
ঐ নাম্বার গুলা থেকে সব থেকে ছোটো এবং পজিটিভ যে নাম্বার টা মিসিং সেটা আমাদেরকে বের করতে হবে।

যেমন,
N = 5, Array[5] = {1, 2, 3, 4, 5}
এখানে মিসিং পজিজিটিভ এবং ছোটো নাম্বার টা হচ্ছে 6
আবার,
N = 5, Array[5] = {0, -10, 1, 3, -20}
এখানে মিসিং পজিটিভ এবং ছোটো নাম্বার টা হচ্ছে ২


প্রবলেম সলুশ্যন আইডিয়া খুবই সোজা, ইলিমেন্ট গুলাকে সর্ট করে অথবা সেটে রেখে মিসিং নাম্বার বের করা যেতে পারে খুব সহজেই। তাহলে এটা Hard ক্যাটাগরির প্রবলেম কেনো ?

আমাদেরকে এই প্রবলেম টা এক্সট্রা কোনো মেমোরি ইউজ না করে অর্থ্যাত O(1) এবং লিনিয়ার অর্থ্যাত O(N) এ সলভ করতে হবে।


আইডিয়াঃ

প্রথম কেইজ,
সব থেকে ছোটো মিসিং পজিটিভ নাম্বার কত হইতে পারে ? 1 (One), Right ?
হ্যা,
এখন পুরো এরেতে যদি ১(এক) না থাকে তাহলে ১ ই আমাদের কাঙ্ক্ষিত রেজাল্ট।

দ্বিতীয় কেইজ,
সহজ চিন্তা, ১ থেকে N এর মধ্যে যদি রেজাল্ট এক্সিস্ট না করে তাহলে রেজাল্ট অবশ্যই N+1, উপরের প্রথম উদাহরন টা।
এই কেইজের হিসাব আলাদা ভাবে করার দরকার নাই, বোঝার সুবিধার্থে বললাম।

তৃতীয়  কেইজ,
আমাদের কাঙ্ক্ষিত রেজাল্ট সবসময় ১ থেকে N এর মধ্যে এক্সিস্ট করবে একটু চিন্তা করলেই বোঝা যাবে। অর্থ্যাত যেকোনো নেগেটিভ নাম্বার এবং N এর থেকে বড় নাম্বার গুলা কে আমরা ইগ্নোর করবো।

ইগ্নোর ব্যাপার টা আরেকটু ভালোভাবে বলি,
উপরের দ্বিতীয় উদাহরন টা খেয়াল করি,

    Index =  0     1   2  3   4
Array[5] = {0, -10, 1, 3, -20}

এখানে মিসিং পজিটিভ নাম্বার ২, যে নাম্বার গুলা আমাদের দরকার নাই অর্থ্যাৎ নেগেটিভ এবং N এর থেকে বড় ঐ নাম্বার 
গুলাকে আমরা 1 দিয়ে Replace করে দিবো।
আর হ্যা, Zero কেও 1 দ্বারা রিপ্লেস করে দিবো। 

তাহলে এখন Array টা দাঁড়ায়,
Array[5] = {1, 1, 1, 3, 1}

খেয়াল করলে দেখা যাবে এই Array তে ১ থেকে N এর বাইরে কোনো নাম্বার নাই, কারন আমরা আগেই বলছিলাম আমাদের রেজাল্ট ১ থেকে N এর মধ্যে এক্সিস্ট করবে, আর আমরা সেভাবেই আগাচ্ছি।

এখন এই Array তে ছোটো একটা Operation করবো, 
বর্তমান পজিশন যদি i হয়, তাহলে 
Index = Array[i] - 1; // এটা দিয়ে আমরা একটা আমরা নতুন একটা Index বানাইলাম, মাইনাস ১ করলাম কারন, আমাদের Array 0 based.

এখন Array[Index] এ যেই ভ্যালু আছে , সেটা যদি পজিটিভ হয় তাহলে সেটাকে নেগেটিভ করে দিবো, আর যদি আগেই নেগেটিভ করা থাকে তাহলে ইগ্নোর করবো ।
এইভাবে সব গুলা ভ্যালুকে এইভাবে মডিফিকেশন করার পর , প্রথম যে Index এর ভ্যলু পজিটিভ পাবো, সেই Index+1 ই হবে আমাদের কাঙ্ক্ষিত রেজাল্ট।

Lets Modify,
    Index =  0   1  2  3  4
Array[5] = {1, 1, 1, 3, 1}

i = 0,
Index = Array[0] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1
New Array,
    Index =  0   1   2  3  4
Array[5] = {-1, 1, 1, 3, 1}

i = 1,
Index = Array[1] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1 // already -1 , no need to change

New Array,
    Index =  0   1    2  3  4
Array[5] = {-1, 1, 1, 3, 1}


i = 2,
Index = Array[2] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1 
// already -1 , no need to change

New Array,
    Index =  0   1   2  3  4
Array[5] = {-1, 1, 1, 3, 1}


i = 2,
Index = Array[2] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1 
// already -1 , no need to change

New Array,
    Index =  0   1   2  3  4
Array[5] = {-1, 1, 1, 3, 1}


i = 3,
Index = Array[3] - 1 = 3-1 = 2
Array[Index] = Array[2] = -1 


New Array,
    Index =  0   1   2  3  4
Array[5] = {-1, 1, -1, 3, 1}

i = 4,
Index = Array[4] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1 
// already -1 , no need to change

New Array,
    Index =  0   1   2  3  4
Array[5] = {-1, 1, -1, 3, 1}


So, we got our final Modify array,

    Index =  0   1   2  3  4
Array[5] = {-1, 1, -1, 3, 1}

এখানে প্রথম থেকে ১ নাম্বার Index এর ভ্যালু পজিটিভ, তাহলে ১+১ = ২ আমাদের মিসিং পজিটিভ নাম্বার।

এখনোও বুঝতে না পারলে কোড

Sunday, August 1, 2021

Trapping Rain Water

Problem:

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

Example:

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.





Approach:
This Problem is almost similar to this problem, so we can assume that we can solve this problem using the two-pointers method. But before move on to the two-pointers method, let's try to solve this problem using the forward and backward array methods. 

Previously we have solved another forward and backward array method, named "Maximum Subarray Sum with One Deletion". 


Now, let's try to visualize the problem.

We have to calculate the maximum traping water area, that would be,
    area = Height * Width
=>area = min(left_block_height, right_block_height) - current_height * 1

Width 1, that is given.

Now, why is this happening!
We have to consider every single position.
Suppose we are at position 'x' , if x-1 block is equal to or smaller than 'x' block, then we can't trap water at 'x' position. The same case at x+1 right block hold. Now, suppose the left block is the bigger and the right block, then we can't make an area like (bigger_block - current_block), because from right block water will be overflowed.

Now, How can we calculate the left max and the right max! simple, we will consider two arrays, named Forward array, and another one is a backward array.

Suppose, in 'x' position value of Forward array give a max height consider from 0th index to current index, Backward array will be same but from right.

Complexity, Time Complexity O(n), and Space Complexity O(n), because Forward and backward arrays taking extra memory.
See the code for a better understanding,


See, we illustrate already, if n < 3 then its not possible to trap any water into this, otherwise we have to calculate.

Sorted block also not possible, but we don't need to consider this one.

Then, we are taking only positive height.

Friday, July 30, 2021

4Sum equal Target

Problem:

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

Constraints:
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

Example,

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

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]], there are three quadruplets possible, but we have to print unique quadruplets.

Approach:
Again this problem is similar to previous all 3Sum problems, This problem also can be solved using the "Two Pointers" method.
let's try to visualize,

We saw that constraints are very low nearly 200, but we can't solve this problem in  O(n^4) approach, but we can solve this problem easily in O(n^3) approach. Initially, we target the first sum of two values,

then using the two pointers we will search for another sum of two values. Thats how we can solve this problem, simply after checking our current target we can move our pointers. See the code for a better understanding.

Here, we have to handle another case, since we have to print unique 
quadruplets, so we can use a set vector for using all quadruplets, then simply we can push it to a 2D vector.


Thursday, July 29, 2021

3Sum Smaller

Problem:
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition
nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1], [-2, 0, 3]

Approach:
Again this problem is similar to the previous 3Sum and 3Sum Closest problems. This problem also can be solved using the Two pointers method. Let's illustrate,
Now how can we move our pointers right? see, if the current sum is less than the target that means from right pointer to left pointer all will be included in our answer because they are all smaller than the target because they are already in sorted order. So if the current sum is smaller than the target then we will move our left pointer forward otherwise we will decrease the right pointer. See the code for a better understanding.



3Sum equal Zero

Problem:

Given an integer array nums, return all the triplets [ nums[i], nums[j], nums[k] ] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example, nums = [-1,0,1,2,-1,-4], Output: [[-1,-1,2],[-1,0,1]]

Approach:
This Problem is similar to this problem, again we will solve this problem using the "Two Pointers" method. Just simply we will avoid the duplicates indexes.

Simple Code:


Wednesday, July 28, 2021

3Sum Closest

Problem;
Given an array of n integers and an integer target, find three integers in the array such that the sum is closest to the target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example, [-1, 2, 1, -4], target =  1, the sum should be 2, we choose (-1, 2, 1) sum is 2
Remember you have to
choose 3 integers, it's not required to they should be contiguous.

Approach:

We can solve this problem using the "Two pointers"
method. let's illustrate,

Here we tried to visualize two pointers method. While Calculating results we have to increase the left index or decrease the right index, simply we can do this by checking the case. When we got our answer, simply we will break the loop and will return our answer. Try to code your own, if you can't check the code given below.


Tuesday, July 27, 2021

Sum of Subarray Minimums

Problem:
You are given an array of integers, find the sum of all minimum values of every subarray of that given array.

size of array <= 3*10^4 >= elements of array

Example: nums = [2,1,3]

subarray     minimum value
2                2
2, 1            1
2, 1, 3        1
1                1
1, 3            1
3                3
-----------------
        sum = 9, that's the answer.


Subarray Sum length at least two, that's are multiple of K

Problem:
Given an integer array nums and an integer k, return true if nums have 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 y such that x = y * k.0 is always a multiple of k

Example, nums = [9, 5, 1, 2, 10] and k = 8, the ans should be true, because subarray sum[5,1,2] = 8 is divisibke by 8

Approach:
This problem is very similar to this problem.
Again this problem can be solved using the prefix sum method. Every time we will mark the value of modulo that can be found from (current Prefix sum value modulo K)

let's illustrate,
See, how it works, we build a prefix sum array, after that every time we will mark the value of (pSum%k with its position) if we haven't met with this value-position before. See, here first we got remainder 1 in position 0 after that again we got the same remainder at position 3, that means,3-0 = 3 elements after position 0, their sum will be divisible by k. 
Lets, check [5,1,2] from position 1 to 3, their sum is 8 that is divisible by 8


Simple code, after each operation, we have to check the length of the subarray is greater than or equal to two(2) or not.

Saturday, July 24, 2021

Maximum Size Subarray Sum Equals k

Problem:

Given an array nums and a target value k, find the maximum length of a subarray that sums to k.
If there isn't one, return 0 instead.

Example:
nums = [1, -1, 5, -2, 3], k = 3, maximum length should be 4, that is [1,-1,5,-2,3]
nums = [-2, -1, 2, 1], k = 1 maximum length should be 2, that is [-1,2]

Approach: This Problem is very similar to this problem, Just we have to modify it a little bit. Again we will solve it using the Prefix sum method. in every ith position, we will check have we met the (pSum - k) value previously or not, then simply we will choose maximum length (i-j+1) Simple code:

Firstly we set 0 value to -1, then we check every time we have met it or not.

Minimum Size Subarray Sum greater or equal K

Problem:
Given an array of positive integers nums and a positive integer target, return the
minimal length of a contiguous subarray of which the sum is greater than or equal(>=) to target. If there is no such subarray, return 0 instead.

Example, nums = [2,3,1,2,4,3] and target = 7, the minimum subarray length should be 2, that is [4,3]


Approach:
We can solve this problem using two methods. The first one is the Prefix sum + Binary search approach and another one is the Two pointer approach.

Let's discuss the first one,
We all know how Prefix sum works, in every ith position it will store the previous all elements sum including current(ith) position, right?
So, now let's illustrate it.

After building the prefix sum array we have to make some observations.

~How can we get our target value !
~How can we choose minimal length subarray
Suppose we're at a position 'i' and we need 'X' number, we can get it if and only if there is another value 'Y', that is,
Current[i] - X = Y
It's really easy to understand,
     prefix[i] - prefix[j] = target
=>prefix[i] - target = prefix[j]
Hence the prefix array is sorted, for finding the prefix[j] we can do a binary search( upper bound can do this). If we get the position of prefix[j] we can simply update our answer by (i-j+1)

Time Complexity : O(n*log(n)), log(n) for binary search

Simple Code:



Friday, July 23, 2021

Subarray Sums Divisible by K

Problem:

Given an array "nums" of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by k.

Example, nums = [4,5,0,-2,-3,1], k = 5 ans should be 7
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3] the sum of this subarrays are divisible by 5.


Approach:

This Problem is similar to Subarray Sum Equals K , the difference is here  we have to find number of subarray is divisible by K.

Approach will be same as before, in every position of given array we will check have we already met its remainder (pSum%k)  or not.
Similarly we will maintain A prefix sum and a Hashing Map.

Corner Case: Hense, there will be negative value, so its possible to have negative ramainder, so we have to make it positive by adding +k.

Simple Code:
Subarray Sums Divisible by K
Again, we count every occurences of remaider that we already met.


Now we will see how it works actually.
See, we calculating result help with prefix sum. Means that every time we need index 'j'(j < i) that is (pSum[i] - pSum[j])%k==0

Now from modular arithmatics, 
     (pSum[i] - pSum[j]) = k*X
=>pSum[j] = pSum[i] - k*X
=>pSum[j] % k = (pSum[i] - k*X)%k [taking mod both sides]
=>pSum[j] % k = (pSum[i] % k - k*X%k)%k [distributive]
=>pSum[j] % k = (pSum[i]%k)%k [k*X%k will be 0]
=>pSum[j] % k = pSum[i]%k

so, we need to find the occurences of pSum[j]%k.

Subarray Sums Equals K

Problem:
Given an array of integers 'nums' and an integer 'K', return the total number of continuous subarrays whose sum equals to 'K'.

Example, [1,2,3], K = 3, total subarray whose sum equal to 3 will be 2, thats are [1,2] and [3]


Approach:

We can solve this problem by a little observation, just think we need k - currnet value instead of k. We can maintain a prefix sum value and a "seen" hashmap, "seen" will tell us how many times we already found the  value we need (current prefix sum - K value)



Basicaly The Hashmap "Seen" we used as a frequency table, every time it store the occurences of 
current prefix sum - K value.

We collect the occurences of 
current prefix sum - K and we store in ans variable.

Now the question is why we need to count the occurences of the value we previously met !

See, in the second example the last Prefix value is 21,
now if we count 21-7 = 14 only 1 , thats not valid because if we include [-2,2] with [1,4] that will be another valid subarray.

When we search for 14 in Prefix sum array we find it on 2 and 4 indexes.
The logic here is that 14 + 7 = 21 so the array between indexes
~ 3 to 7 (-2 2 1 4 2)
~ 5 to 7 both have sum 7 ( 1 4 2)
The sum is still 7 in this case because there are negative numbers that balance up.
So if we consider count++ we will have one count less as we will consider only array 5 to 7 but now we know that 14 sum occured earlier too so even that needs to be added up so occurences of (sum-k).


Simple code:


Thursday, July 22, 2021

Sum of All Odd Length Subarrays

Problem:

Given an array of positive integers, calculate the sum of all possible odd-length subarrays.
A subarray is a contiguous subsequence of the array.

Example,
arr = [1, 4, 2, 5, 3]

The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1, 4, 2]  = 7
[4, 2, 5] = 11
[2, 5, 3] = 10
[1, 4, 2, 5, 3] = 15

If we add all these together we get 1+4+2+5+3+7+11 = 58

Approach:
From Subarray Sums the occurrences we can divide by 2 and can take it to calculate the odd length subarray sum.

Simply by traversing the whole array we can do,

occurences = ((i + 1) * (n - i))
result += (arr[i] * (  (occurences + 1)/ 2 ) ) // taking ceil

Subarray Sums

Problem:

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

For example, the array [1, 3, 7] has seven subarrays(N*(N+1)/2):

[ ]    [1]   [3]   [7]   [1, 3]   [3, 7]   [1, 3, 7]

Notice that [1, 7] is not a subarray of [1, 3, 7], because even though the values 1 and 7 appear

in the array, they're not consecutive in the array. Similarly, the array [7, 3] isn't a

subarray of the original array, because these values are in the wrong order.

The sum of an array is the sum of all the values in that array. Your task is to write a function that takes as input an array and outputs the sum of all of its subarrays.

For example, given [1, 3, 7], you'd output 36, because

[ ] + [1] + [3] + [7] + [1, 3] + [3, 7] + [1, 3, 7] = 0 + 1 + 3 + 7 + 4 + 10 + 11 = 36


Approach:

The problem is very easy to understand. Now First, try to solve this by the brute force approach. 

Here we visit every length subarray, this will cost O(n^3), which is huge. We can reduce it to O(n^2), but that's not enough.


We can improve our time complexity by a little observastion, just think about every numbers occurences in their total subarray's.

Just look at the array [1,2,3], subarray's are,

[1] [2] [3]

[1,2] [2,3]

  [1,2,3]

Notice how many copies of each element there are. There are three 1's, four 2's, and three 3's.



Occurences can be calculate by simple formula (i + 1) * (arr.length() - i)
So, By traversing the whole array we can calcualte our subarray sum by this formula
result += arr[i] * (i + 1) * (arr.length() - i)

Maximum Subarray Sum with One Deletion

Problem:
Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1, [1, -2, 0, 3] ~ The maximum sum should be 4, we choose all elements and remove -2
Example 2, [1, -2, -2, 3] ~ The maximum sum should be 3, we choose [-2,3] and we remove -2
Example 3, [-2, -3, 4, -1, -2, 1, 5] ~ The maximum sum should be 9, we choose [4, -1, -2, 1, 5] and remove -2

Approach:
So, our main goal is to Choose a subarray which size is at least 2, and after removing 1 element we have to make the sum of choosing subarray after that we have to maximize this sum.

We can solve this problem by building a forward and a backward array, and its kind of DP.

What we say earlier, we will make two array of maximum subarray sum from forward(left to right) and another from backward(right to left).

Formaly what we can get from this array ?
suppose forward array, in every element of ith position will say this is the maximum subarray sum untill this position.

Build forward array bay maximizing previous value of forward element + current value of original element with current value of original element.

Similarly backward array will be build this way. 





Firstly we make forward and backward array, at the same time we maximize an Ans value by checking current value of forward and backward array.



And finally we traverse whole array and  tried to remove every element and take sum of forward or backward maximum subarray value.



Maximum Subarray Sum


Problem:
Given an integer array A, find the contiguous subarray (containing at least one number) which has the largest sum.

Example:
A = [-2,1,-3,4,-1,2,1,-5,4], The largest sum should be 6, we choose [4,-1,2,1] subarray.

Approach:
There are few approaches to solve this problem.
We are going to solve it by 
Kadane's Algorithm, and Prefix Sum.


In Kadanes Algorithm we will do three operations:

1.  Add Current elements of the array to a variable named Sum.
2. Update Largest Sum with Sum.
3. If the current Sum is negative make it Zero.






This is the code of Maximum Subaarray sum using the Kadanes Algorithm. Simply we traverse the whole array by doing three operations.




In Prefix Sum Approach we usually do two types of operations, Before calculating the largest subarray sum, we have to build a prefix array.
By traversing every element of prefix array, 
1. Every time we remove a minimum prefix value from the current prefix value by comparing the largest sum.
2. Update minimum value