DS practice questions - tarunchhabra/parakalo GitHub Wiki
1) Remove Even- Educative
MA- Create result array with length= original array length and then loop and check if arr[i] is odd and insert that odd number in result array.
EA- Same as LL
LL- How to find the length of result array. Find the count of elements in original array and create new array with oddCount.
2) Max Consecutive Ones - LeetCode
MA- Using nested loop to find the count of 1
LCA- loop over array and count++ whenever 1 is found and break if 0 is found. https://massivealgorithms.blogspot.com/2017/01/leetcode-485-max-consecutive-ones.html GFG
3) Find Numbers with Even Number of Digits- LeetCode
LL- How to compute the number of digits of a number ? Divide the number by 10 again and again to get the number of digits.
4) Kids With the Greatest Number of Candies - LeetCode
MA- Find max and add e to all elements and check whether sum is >= max
LCA- Use greedy approach. For each kid check if candies[i] + extraCandies ≥ maximum in Candies[i].
5) How Many Numbers Are Smaller Than the Current Number - LeetCode
MA- BF Approach using nested loops, Brute force for each array element.
LCA- In order to improve the time complexity, we can sort the array and get the answer for each array element.
LL- sorting the original array can reduce the time complexity...like in this case it changed from O(N^2) to O(NlogN)
6) Decompress Run-Length Encoded List
MA- find the length of result array by finding sum of values at even index of array. Then loop over array from 0 to n with i=i+2 finding the frequency of each element and then nested loop from 0 to < freq to insert element in result array.
7) Create Target Array in the Given Order - LeetCode
MA- Loop over both arrays simultaneously and for every value I in index array Insert the value at I in nums array to result array. Check if the index array value is < current value of i that means we are reinserting at already reinserted place in result array.
8) Duplicate Zeros - LeetCode
-- Solved but Understand again.
9) Merge 2 sorted arrays- Educative/Leetcode
MA- BF using 2 nested loops
EA- BF and 2 Pointer approach
LL-
--------------- continues...
####### Two Pointer Approach-
-
In problems where we deal with sorted arrays (or LinkedLists) and need to find a set of elements that fulfill certain constraints, the Two Pointers approach becomes quite useful.
-
he set of elements could be a pair, a triplet or even a subarray.
-
we use 2 pointers- i and j i moves in left(reverse) direction and j moves in right(forward direction). Let's apply this approach in below questions.
See https://www.educative.io/courses/grokking-the-coding-interview/xlK78P3Xl7E
6) Find Two Numbers that Add up to "n" - Educative
MA- Brute Force- Traverse the whole array of the given size. For each element in the array, check if any of the two elements add up to the given number n. Use a nested for-loop for this purpose and iterate over the entire array for each element.
LCA- Approach-1) A better way to solve this is by first sorting the array and then use 2 Pointer approach (pending). O(n^2). Note: To apply 2 ptr approach here the array should be sorted.
Approach-2) Using Hash Table O(n)
- Squares of a Sorted Array -
MA- Intuition and Algorithm- Create an array of the squares of each element, and sort them.
LCA- Two Pointer.Our strategy is to iterate over the negative part in reverse, and the positive part in the forward direction. We can use two pointers to read the positive and negative parts of the array - one pointer j in the positive direction, and another i in the negative direction.
https://leetcode.com/articles/squares-of-a-sorted-array/
3) Shuffle the Array- LeetCode
MA- Find mid and insert in array value at current index and then insert value at mid + i index
LCA- Use two pointers to create the new array of 2n elements. The first starting at the beginning and the other starting at (n+1)th position. Alternate between them and create the new array.
LL- Need to understand 2 pointer approach...not understood yet.
**************** understand educative approach for questions 8
**************** understand solved questions and write your approach here
**************** udemy course DSA
################ Basic concepts
find max number Find digit of a number shift elements to right Brute force Greedy approach 2 pointer approach