This repository contains solutions of coding problems for interviews.
The README, problem details, and solutions are updated using a PowerShell script.
| SL No | Problem Name w/ Difficulty | Leetcode | Lintcode | Solution | Notes |
|---|---|---|---|---|---|
| 01 | 88. Merge Sorted Array 🟢Easy |
88 | — | 01-Apr-24 Java |
Set k as the new length of the merged array. Iterate the array from the end, if nums1[i]>nums2[j] add nums1[i] to kth index in nums1, reduce index i, k. Else add nums[j] to kth index and reduce index j, k. If elements still in nums2, iterate and add to kth index, reduce j,k. |
| 02 | 27. Remove Element 🟢Easy |
27 | 172 | 01-Apr-24 Java |
Initialize index i=0, iterate the array and if the element is not equals to val, add it to i index, increment the index i. Return i. |
| 03 | 26. Remove Duplicates from Sorted Array 🟢Easy |
26 | 🔒 100 | 01-Apr-24 Java |
Set an index len=0 and iterate the array from index 1, if the current element is not equal to element at len, increment len and set it as element at len. Return len. |
| 04 | 80. Remove Duplicates from Sorted Array II 🟡Medium |
80 | 101 | 01-Apr-24 Java |
Initialize len, iterate the array, if len<2 or if current element greater than previous two elements in the modified array, add it and increment len. Return len. |
| 05 | 169. Majority Element 🟢Easy |
169 | 46 | 01-Apr-24 Java |
Iterate the array, if count is 0, set the current element as majority. If current element==majority increment count, else decrement it. Return majority. |
| 06 | 189. Rotate Array 🟡Medium |
189 | 1334 | 01-Apr-24 Java |
Adjust k to the length of the array, reverse the whole array, then reverse the first k element, and then reverse the rest of the array. |
| 07 | 121. Best Time to Buy and Sell Stock 🟢Easy |
121 | 149 | 01-Apr-24 Java |
Initialize left and right pointers. Iterate the array, if prices[right]>prices[left] calculate maxProfit, else update left=right. Return maxProfit. |
| 08 | 122. Best Time to Buy and Sell Stock II 🟡Medium |
122 | 150 | 01-Apr-24 Java |
Iterate the array and calculate sum of all increases in stock price from the previous in maxProfit. This is because we can sell immediately when price goes up and buy again when same or price goes down. Return maxProfit. |
| 09 | 55. Jump Game 🟡Medium |
55 | 116 | 02-Apr-24 Java |
Iterate the array till i<=jump, update jump with i+nums[i]. Return if jump>=nums.length-1 ,i.e can jump to last index. |
| 10 | 45. Jump Game II 🟡Medium |
45 | 117 | 02-Apr-24 Java |
Set curJump=maxJump=nums[0]. Iterate the array till the second last element. Calculate the maxJump=i+nums[i]. If i==curJump, increment jump count and update curJump as maxJump. Return jump count. |
| 11 | 274. H-Index 🟡Medium |
274 | 1304 | 02-Apr-24 Java |
Initialize a count array to count the number of citations. Iterate the array and increase the count(if num>n) set it as n as h-index cannot be more than n. Set a sumCount and iterate the the count array from n to 0, add count[i] to sumCount. If sumCount is >= i, i.e. there are atleast i papers with atleast i citations(h-index). Return i. Outside return 0. |
| 12 | 380. Insert Delete GetRandom O(1) 🟡Medium |
380 | 657 | 02-Apr-24 Java |
Declare a map to store the value key w/ index, a list for values and a random variable. Inside the constructor initialize the 3 variable. In insert(val) return false if val already present. Else add val to the list and also add the val with index to map. Return true. In remove(val) return false if val not present. Else get the index of the val, get the last element from the list, set it at index and also update the last element index in the map. Form list remove the last element and form map remove val. Return true. In getRandom() , Generate an random within list.size() and return the element at this index from the list. |
| 13 | 238. Product of Array Except Self 🟡Medium |
238 | 1310 | 02-Apr-24 Java |
Initialize result array. Calculate prefix product(numbers in the left) in the result array. Iterate result array from the end, do postfix product(numbers in the right) in the result array. Return result array. |
| 14 | 134. Gas Station 🟡Medium |
134 | 187 | 03-Apr-24 Java |
totalGasStations is the length of the gas array. Iterate both the array and add to current tank gas[i] - cost[i]. If tank<minGas update minGas and update start as next index. If tank is -ve return -1 as we cannot complete the circuit. If start == totalGasStations return 0 as we start at the first index, else return start. |
| 15 | 135. Candy 🔴Hard |
135 | 412 | 03-Apr-24 Java |
We use two arrays left and right to count number of candies for each neighbor. We initialize both with 1 as all students gets atleast 1 candy. For each student if its rating is more than left increment candy count one more than left. Similarly iterate from the right, if candy count more than next increment candy count as 1 more than new. Count the totalCandies by adding max from left and right array for the student. Return totalCandies. |
| 16 | 42. Trapping Rain Water 🔴Hard |
42 | 363 | 04-Apr-24 Java |
Use two pointer to iterate from both ends, update maxLeft and maxRight height. if maxLeft<maxRight add current empty height from the left to totalWater and increment left. Else add current empty height from right to totalWater and increment right. Return totalWater. |
| 17 | 13. Roman to Integer 🟢Easy |
13 | 419 | 04-Apr-24 Java |
Iterate the string from behind, get the value of the numeral using switch case, if the value*4 is less than current result, subtract it (as smaller numeral before larger appears only 1/5 and 1/10 of larger numeral. Eg: IV = 4 = 1*4<5; so subtract.) else add it. Return result. |
| 18 | 12. Integer to Roman 🟡Medium |
12 | 418 | 04-Apr-24 Java |
Write string arrays for ones,tens,hundreds and thousands places Roman numerals. Use a mutable string roman to append the number places as roman numerals, starting at thousands place. Return the roman converted to string. |
| 19 | 58. Length of Last Word 🟢Easy |
58 | 422 | 04-Apr-24 Java |
Iterate the string, from the end, if character is not ' ' increase len. If ' ' is found and len!=0 i.e last word is found, break the loop, return the len. |
| 20 | 14. Longest Common Prefix 🟢Easy |
14 | 78 | 04-Apr-24 Java |
Return "" if array is empty. Set prefix as the first word. Iterate the array from the second word. While the array does not start with prefix remove one character from the end of prefix. If the prefix becomes empty return "". Outside the loop return prefix. |
| 21 | 151. Reverse Words in a String 🟡Medium |
151 | 53 | 04-Apr-24 Java |
Extract the words to an array. Iterate the array from the end and append the words to the result. Return result. (Also a faster solution using while to iterate the string and skip ' ', and add the words to result) |
| 22 | 6. Zigzag Conversion 🟡Medium |
6 | 1363 | 04-Apr-24 Java |
Return string if numRows==1. Initialize a string array of length min(numRows,s.length). Initialize curRow = 0 and goingDown = false. Iterate each character from the beginning and append it to current row. If curRow=0 or =numRows-1 then change direction. Increment curRow if goingDown else decrement. Append all the rows to a string result and return it. |
| 23 | 28. Find the Index of the First Occurrence in a String 🟢Easy |
28 | — | 04-Apr-24 Java |
If needle is empty return -1. Return the indexOf first occurrence of needle. |
| 24 | 68. Text Justification 🔴Hard |
68 | 1361 | 04-Apr-24 Java |
Iterate the words, add it to the currentLineWords list till currentLineLength <=maxWidth. If it is the last word in the words list or currentLineWords is 1, left justify and do right padding, add it to result list, and continue to next iteration. Calculate the spacePerGap, extraSpaces and create the line form currentLineWords and add it to the result list. Return the result list. |
| SL No | Problem Name w/ Difficulty | Leetcode | Lintcode | Solution | Notes |
|---|---|---|---|---|---|
| 01 | 125. Valid Palindrome 🟢Easy |
125 | 415 | 04-Apr-24 Java |
Iterate the character from start and end, skip non-alphanumeric characters. If charAt(start) != charAt(end) return false immediately. Increment pointers. If all characters from both ends are equal return true. |
| 02 | 392. Is Subsequence 🟢Easy |
392 | 1263 | 04-Apr-24 Java |
Initialize two pointers ptrS and ptrT for s and t string. Iterate the character of t string, if s[ptrS]==t[ptrT] increment ptrS , if ptrS==s.length() return true. Increment ptrT. Return false if all characters in s not in t. |
| 03 | 167. Two Sum II - Input Array Is Sorted 🟡Medium |
167 | 🔒 608 | 04-Apr-24 Java |
Iterate from both ends and calculate sum. If sum==target return {start+1,end+1}, else if sum<target increment start, else decrement end. Return {-1,-1} if no sum found. |
| 04 | 11. Container With Most Water 🟡Medium |
11 | 383 | 04-Apr-24 Java |
Iterate from both ends, calculate length=right-left and breadth=min(left,right). Calculate area and update maxArea. Increment left till higher breadth is found, decrement right till higher breadth is found. Return maxArea. |
| 05 | 15. 3Sum 🟡Medium |
15 | 57 | 04-Apr-24 Java |
Sort the nums array. Iterate the array with i and skip duplicate. Set left as i+1 and right as end of nums, iterate the rest of the array until left==right. Find threeSum=nums[i]+nums[left]+nums[right]. If sum>0 decrement right, else if sum<0 increment left, else if sum=0 add nums[i],nums[left],nums[right] to the result array. Increment left and skip duplicates from left. Return results array. |
| SL No | Problem Name w/ Difficulty | Leetcode | Lintcode | Solution | Notes |
|---|---|---|---|---|---|
| 01 | 209. Minimum Size Subarray Sum 🟡Medium |
209 | 406 | 05-Apr-24 Java |
Iterate the array using right pointer and add it to the sum, if sum>=target save the current window length to ans, remove left element from sum and increment left pointer. Increment right pointer. If no window of sum>=target found return 0 else return ans. |
| 02 | 3. Longest Substring Without Repeating Characters 🟡Medium |
3 | 384 | 05-Apr-24 Java |
Use a hashSet to store already visited elements. Iterate the string using right pointer if character not in hashSet, add it to hashSet, save the current window length and increment right pointer. Else if element already present, remove the left most element from hashSet, and increment left pointer. Return the max window length. |
| 03 | 30. Substring with Concatenation of All Words 🔴Hard |
30 | 1362 | 05-Apr-24 Java |
Initialize a result list. Return empty list if word count or s string length equal to zero. Use a wordCount map to update word frequencies in words array. Store number of words in wordNum and length of each word in wordLen. Iterate using for-loop i till wordLen as the substring can start from any index till wordLen, and initialize left=right=i, count=0, also create a map currentCount to count word count in current window substring. Iterate the string from i, with steps of wordLen using right pointer, extract word and increment right counter. If word not in wordCount, reset count=0, set left=right and clear currentCount. Else put/increase word in currentCount, increase count, If current word in currentCount more than in wordCount, remove left word from currentCount, increment left pointer, decrease count. If count==wordNum, window has all the words add left to result. Return result. |
| 04 | 76. Minimum Window Substring 🔴Hard |
76 | 32 | 06-Apr-24 Java |
Count frequency of each character and total number of unique character as need for the t string. Iterate the s string increment have, if have==need, if current window less than resLen update resIndex and reLen. Increment left pointer and decrement count of character in window, also reduce have if current character is a unique character. If resLen was update return string from resIndex to resLen or return empty string. |