Neetcode 150 🗿

Typescript solutions to Leetcode problems from the Neetcode 150 list

Useful Links 

Leetcode Website
neetcode.io roadmap
Neetcode's YouTube channel link
Neetcode's Leetcode solutions repository
Vitest unit test framework

Grandma's Place 👵🏚️

Problems worth a revisit (This list is a little personal)

• Valid Sudoku
• Trapping Rain Water
• Generate Parentheses
• Largest Rectangle in Histogram
• Search In Rotated Sorted Array
• Longest Repeating Character Replacement
• Copy List With Random Pointer
• Find the Duplicate Number

Contributing

• Only typescript(.ts) files are allowed
• Neatly formatted(prettier, ESlint) code
• Add link to related Neetcode solution video
• Only add explanation if your approach is better than Neetcode's
• Add time/space complexity with shortest possible explanation
• Code has to be readable(descriptive variable names, etc.)
• Add relevant comments wherever necessary
• If possible write tests using vitest
• PR Example:
  • src/longest-commmon-prefix.ts

  export const longestCommonPrefix = (s: string[]): string => {
    s = s.sort()
    let i: number = 0
    let first: string = s[0] // first string in array
    let last: string = s[s.length - 1] // second string in array
    // i should not exceed the length of the shorter of the first and last string 
    let shorterString: number = Math.min(first.length, last.length)
    while (first[i] === last[i] && i < shorterString) i++
    return first.slice(0, i)
  }

  • tests/longest-commmon-prefix.test.ts

  import { longestCommonPrefix } from "../src/longest-common-prefix"
  import { expect, test } from "vitest"
  // use descriptive test names
  test('finds the longest common prefix in a collection of strings', () => {
    let strs1: string[] = ["flower", "flow", "flight"]
    let strs2: string[] = ["dog", "racecar", "car"]
    expect(longestCommonPrefix(strs1)).toEqual("fl")
    expect(longestCommonPrefix(strs2)).toEqual("")
  })

  • README.md
  * [x] [Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/) * Neetcode's solution: * Explanation Instead of using the Neetcode's approach we use another trick which is to sort the array & then only compare the first and the last string of the array instead of comparing all the strings which would result in a better time complexity. This solution works because Javascript sorts the array by strings. This will closely group the strings that are more alike & the strings that are least alike will go the extreme ends of the array after sorting and these strings are the ones that will result in the shortest common prefix. This is more obvious from the below node REPL output: ```js > let s = ["chicken", "duck", "dutch", "children", "parrot", "china"] [ 'chicken', 'duck', 'children', 'china' ] > s.sort() [ 'chicken', 'children', 'china', 'duck'] ``` Although 3 of the 4 strings have the common prefix 'chi', one of them('duck') does not have any common character with any of the other strings so it makes sense to only compare 'chicken' & 'duck' which are least alike.
• Code standard:
  • Use function expression

  // prefer function expression
  export const longestCommonPrefix = (s: string[]): string => {}
  // avoid this to prevent hoisting
  function longestCommonPrefix (s: string[]): string {}

All problems

Arrays & Hashing

• Contains Duplicate
• Valid Anagram
• Two Sum
• Group Anagrams
• Top K Frequent Elements
• Product of Array Except Self
• Valid Sudoku
• Encode and Decode Strings
• Longest Consecutive Sequence

Two Pointers

• Valid Palindrome
• Two Sum II Input Array Is Sorted
• 3Sum
• Container With Most Water
• Trapping Rain Water

Stack

• Valid Parentheses
• Min Stack
• Evaluate Reverse Polish Notation
• Generate Parentheses
• Daily Temperatures
• Car Fleet
• Largest Rectangle In Histogram

Binary Search

• Binary Search
• Search a 2D Matrix
• Koko Eating Bananas
• Find Minimum In Rotated Sorted Array
• Search In Rotated Sorted Array
• Time Based Key Value Store
• Median of Two Sorted Arrays

Sliding Window

• Best Time to Buy And Sell Stock
• Longest Substring Without Repeating Characters
• Longest Repeating Character Replacement
• Permutation In String
• Minimum Window Substring
• Sliding Window Maximum

Linked List

• Reverse Linked List
• Merge Two Sorted Lists
• Reorder List
• Remove Nth Node From End of List
• Copy List With Random Pointer
• Add Two Numbers
• Linked List Cycle
• Find The Duplicate Number
• LRU Cache
• Merge K Sorted Lists
• Reverse Nodes In K Group

Trees

• Invert Binary Tree
• Maximum Depth of Binary Tree
• Diameter of Binary Tree
• Balanced Binary Tree
• Same Tree
• Subtree of Another Tree
• Lowest Common Ancestor of a Binary Search Tree
• Binary Tree Level Order Traversal
• Binary Tree Right Side View
• Count Good Nodes In Binary Tree
• Validate Binary Search Tree
• Kth Smallest Element In a Bst
• Construct Binary Tree From Preorder And Inorder Traversal
• Binary Tree Maximum Path Sum
• Serialize And Deserialize Binary Tree

Tries

• Implement Trie Prefix Tree
• Design Add And Search Words Data Structure
• Word Search II

Heap / Priority Queue

• Kth Largest Element In a Stream
• Last Stone Weight
• K Closest Points to Origin
• Kth Largest Element In An Array
• Task Scheduler
• Design Twitter
• Find Median From Data Stream

Backtracking

• Subsets
• Combination Sum
• Permutations
• Subsets II
• Combination Sum II
• Word Search
• Palindrome Partitioning
• Letter Combinations of a Phone Number
• N Queens

Graphs

• Number of Islands
• Clone Graph
• Max Area of Island
• Pacific Atlantic Water Flow
• Surrounded Regions
• Rotting Oranges
• Walls And Gates
• Course Schedule
• Course Schedule II
• Redundant Connection
• Number of Connected Components In An Undirected Graph
• Graph Valid Tree
• Word Ladder

Advanced Graphs

• Reconstruct Itinerary
• Min Cost to Connect All Points
• Network Delay Time
• Swim In Rising Water
• Alien Dictionary
• Cheapest Flights Within K Stops

1-D Dynamic Programming

• Climbing Stairs
• Min Cost Climbing Stairs
• House Robber
• House Robber II
• Longest Palindromic Substring
• Palindromic Substrings
• Decode Ways
• Coin Change
• Maximum Product Subarray
• Word Break
• Longest Increasing Subsequence
• Partition Equal Subset Sum

2-D Dynamic Programming

• Unique Paths
• Longest Common Subsequence
• Best Time to Buy And Sell Stock With Cooldown
• Coin Change II
• Target Sum
• Interleaving String
• Longest Increasing Path In a Matrix
• Distinct Sub-sequences
• Edit Distance
• Burst Balloons
• Regular Expression Matching

Intervals

• Insert Interval
• Merge Intervals
• Non Overlapping Intervals
• Meeting Rooms
• Meeting Rooms II
• Minimum Interval to Include Each Query

Greedy

• Maximum Subarray
• Jump Game
• Jump Game II
• Gas Station
• Hand of Straights
• Merge Triplets to Form Target Triplet
• Partition Labels
• Valid Parenthesis String

Bit Manipulation

• Single Number
• Number of 1 Bits
• Counting Bits
• Reverse Bits
• Missing Number
• Sum of Two Integers
• Reverse Integer

Math & Geometry

• Rotate Image
• Spiral Matrix
• Set Matrix Zeroes
• Happy Number
• Plus One
• Pow(x, n)
• Multiply Strings
• Detect Squares

JavaScript

• Create Hello World Function (Closure - Day1)
• Counter (Closure - Day2)
• Counter (Closure - Day3)
• Apply Transform over each Element in Array (Transform)
• Filter Elements from Array (Transforms)
• Array Reduce Transformation (Transforms)
• Function Composition
• Allow One Function Call
• Memoize
• Curry
• Sleep
• Promise Time Limit
• Promise Pool
• Cache With Time Limit
• Debounce
• Throttle
• JSON Deep Equal
• Convert Object to JSON String
• Array of Objects to Matrix
• Difference Between Two Objects
• Chunk Array
• Flatten Deeply Nested Array
• Array Prototype Last
• Group By
• Check if Object Instance of Class
• Call Function with Custom Context
• Event Emitter
• Array Wrapper
• Generate Fibonacci Sequence
• Nested Array Generator