daily-leetcode

Daily leetcode problem solution. The README, problems details and solutions are maintained and updated via a Powershell script.

March 2024

See Solutions here

SL No	Program Name w/ Difficulty	Leetcode	Lintcode	Solution	Notes
01	442. Find All Duplicates in an Array 🟡Medium	442	1238	25-Mar-24 Java	Iterate the array. As the numbers in the array are within the size of the array(n), so every number represents a index of the array. Visit the index(nums[i]) and and mark it visited(-ve). If for a index(nums[i]) the value is already -ve, the the nums[i] is a duplicate as it is already visited. Add it to result.
02	41. First Missing Positive 🔴Hard	41	189	26-Mar-24 Java	Iterate the array and put the elements at there correct index in the array. Iterate the array find the smallest position where the index does not match the number. If all numbers in there correct index return n+1.
03	713. Subarray Product Less Than K 🟡Medium	713	1075	27-Mar-24 Java	Sliding window, left=right=0. Iterate the array using right pointer, find the product with the current number. If the product is more than or equal to k, shift the left pointer and divide them from the product. Add the current length of the window to the count. Return count.
04	2958. Length of Longest Subarray With at Most K Frequency 🟡Medium	2958	—	28-Mar-24 Java	Use a HashMap to store the count of the digits encountered. Use sliding window, iterate using right. Increase current digit count, if it more than k, move left pointer and decrease the moved elements count. Find the maximum window length.
05	2962. Count Subarrays Where Max Element Appears at Least K Times 🟡Medium	2962	—	29-Mar-24 Java	Find the maxNum in the array. Iterate using right pointer and if current element is equal to maxNum increase count. When count is equal to k, increment left, and if nums[left]==maxNum, decrease count. Add left to answer, as elements till left sums to count. After iterating, return answer.
06	992. Subarrays with K Different Integers 🔴Hard	992	—	30-Mar-24 Java	Count of atleast k distinct elements - Count of atleast k-1 distinct elements, will give subarray with exactly k distinct elements. To count the subarray, iterate the array and increase the element count, if its count is 1 decrease k. If k==-1, shrink window from left, decrease count and if element removed from window increase k. Add window length(r-l+1) to answer.
07	2444. Count Subarrays With Fixed Bounds 🔴Hard	2444	—	31-Mar-24 Java	Initialize the minIndex,maxIndex and left, right pointers. Iterate the elements, if the element is outside the valid range minK < ele < maxK, update minIndex, maxIndex and left pointer. If current element == minK update minIndex pointer, if current element == maxK update maxIndex pointer. Add to count valid window till current element (min(minIndex,maxIndex)-left). Return count.

April 2024

SL No	Problem Name w/ Difficulty	Leetcode	Lintcode	Solution	Notes
01	58. Length of Last Word 🟢Easy	58	422	01-Apr-24 Java	Iterate the string, from the end, if character is not ' ' increase len. If ' ' is found and len!=0, break the loop, return the len.
02	205. Isomorphic Strings 🟢Easy	205	638	02-Apr-24 Java	Initialize two HashMaps for the two strings. Iterate the string, get the current character for s in c1 and for t in c2. If c1 is mapped to different character than c2, return false. If c2 is mapped to different character than c1, return true. Map c1 to c2 and map c2 to c1. Return true if outside the loop.
03	79. Word Search 🟡Medium	79	123	03-Apr-24 Java	Iterate every cell of the board and do dfs to check if the word can be found starting at cell then return true, if all cells searched and no match found return false. In dfs, if start index of word equals length of word then return true as the word is found. Return false if limits of i and j reached or the current cell in board do not match character of the word. Store the character of at current cell, mark it at visited, traverse in all direction and store in res. Rest cell with the stored character. Return res.
04	1614. Maximum Nesting Depth of the Parentheses 🟢Easy	1614	—	04-Apr-24 Java	Iterate characters of the string, if it is ( increment curDepth count, if curDepth > maxDepth update maxDepth. Else if it is ) decrement curDepth. Return maxDepth.
05	1544. Make The String Great 🟢Easy	1544	—	05-Apr-24 Java	Iterate the characters of the string and add it to the sb stack, if the last element of the stack is equal to the current character but in DIFFERENT CASE, remove last element from the stack and don't add current element, else add current element to the stack. We greedily remove all instances of two adjacent characters that are same letter but in DIFFERENT CASE. Return the sb stack converted to string.
06	1249. Minimum Remove to Make Valid Parentheses 🟡Medium	1249	—	06-Apr-24 Java	Use a stack to keep track of position of (. Iterate the string, if current character is ( push it to stack, else if current character is ), if stack not empty pop last (, if stack empty mark current character as * to be remove as there i no valid ( for the current ). Outside if stack is not empty, i.e there are invalid (, pop temp and and mark them as * to be removed. Return the string after removing the *'s.
07	678. Valid Parenthesis String 🟡Medium	678	1089	07-Apr-24 Java	Initialize two counters, minOpen and maxOpen to keep track of the upper and lower bounds of the (. Iterate the character of the string, if ( increment both counters, if ) decrement both counters but minOpen should not be less than 0, if * decrement minOpen considering * = ( and increment maxOpen considering * = ). If maxOpen<0 then return false as there are more ). Return minOpen==0 as as all ( has ).
08	1700. Number of Students Unable to Eat Lunch 🟢Easy	1700	—	08-Apr-24 Java	Initialize count[2] to count number of sandwiches needed for type 0 or 1. Initialize the count with students preference of sandwiches. Iterate the sandwiches[] if count[sandwiches[i]]==0 return sandwiches.length-i as the rest of the students will not hav there preferred sandwiches. Decrement the count for each sandwich type visited. If traversal over, return 0 as all students have sandwiches to eat.
09	2073. Time Needed to Buy Tickets 🟢Easy	2073	—	09-Apr-24 Java	Initialize time. Iterate the tickets[] if i<=k then add to result min of tickets[i] and tickets[k]. Else add to result min of tickets[i] and tickets[k] -1(as k has already purchased a ticket before them). Return time.
10	950. Reveal Cards In Increasing Order 🟡Medium	950	—	10-Apr-24 Java	Initialize result[], idxDeck=0, idxResult=0, skip=false. Sort the deck in ascending order. Iterate all index of deck. If result[idxResult]==0 and !skip then add the current card in deck to it, increment idxDeck and flip skip, as we will skip next card. If result[i]==0 and skip==true then increment idxResult and also % n to ensures the index cycles back to beginning if it reached end as we are skipping the next elements of the deck. Return result.
11	402. Remove K Digits 🟡Medium	402	1255	11-Apr-24 Java	If k==num.length return "0" as all characters can be removed. Iterate the digits in the string num, add the digit into the stack. If current digit is less than top of the stack pop the top of the stack and decrease k. Create the res string from the stack removing the top k elements, and also removing leading 0s. Return res string.
12	42. Trapping Rain Water 🔴Hard	42	363	12-Apr-24 Java	Initialize totalWater. Use two pointers left and right and iterate the array from beginning and end till left<right. Calculate maxLeftHeight and maxRightHeight from the current left and right pointers. If current maxLeftHeight is less than maxRightHeight, add current empty height from left(maxLeftHeight-height[left]) to totalWater, and increment left pointer. Else add current empty height from right(maxRightHeight-height[right]) to totalWater, and decrement right pointer. Return totalWater.
13	85. Maximal Rectangle 🔴Hard	85	510	13-Apr-24 Java	If matrix is empty return 0. Initialize a histogram array height[]. Iterate the matrix, for each column if current cell is '0' set height[j]=0 else increment the height[j] histogram. Calculate maxArea for the current row using largestRectangleArea(height[]). Return maxArea. Inside largestRectangleArea function, use a stack to store the index and push -1 as a sentinel value. Iterate the height[], while stack not empty and current height < stack top index height, calculate maxArea. Push current index i to stack. If more index left in stack calculate maxArea. Return maxArea.
14	404. Sum of Left Leaves 🟢Easy	404	1254	14-Apr-24 Java	Return 0 if root is null. Initialize sum=0. If left node is a leaf node i.e. no left and right exist, then set its val as sum. Recursively call sumOfLeftLeaves for left and right subtree, add it to sum. Return the total sum.
15	129. Sum Root to Leaf Numbers 🟡Medium	129	1353	15-Apr-24 Java	Do DFS Traversal of the tree starting at root, return the totalSum after the dfs traversal. Inside dfs if node != null then append the current node value to the curNumber*10, shifting curNumber to left and adding the value. If current not is a leaf node i.e node.left = node.right = null then add curNumber to totalSum. Do DFS on left and right subtree.