DSA Arrays Hashing TypeScript

Introduction

Arrays and Hashing is the first category in my post LeetCode Starting Over with NeetCode as they are the most used and fundamental concepts in data structures. This is my approach to solving NeetCode problems.

If you have more problems to add or any specific points you want to discuss, please feel free to share!

Why Arrays and Hashing?
Contains Duplicate (Easy) Solution
Valid Anagram (Easy) Solution
Two Sum (Easy) Solution
Group Anagrams (Medium) Solution
Top ‘𝐾’ Frequent Elements (Medium) Solution
Encode and Decode Strings (Medium)
Product of Array Except Self (Medium)
Valid Sudoku (Medium)
Reference

Why Arrays and Hashing?

Starting with these concepts allows for a solid understanding of basic operations, performance trade-offs, and practical applications in programming and algorithm design.

Arrays are the most used and fundamental data structures, providing a strong foundation for understanding more complex structures. Hash maps, on the other hand, are crucial for efficient data storage and retrieval, making them the second most important and commonly used data structures.

Arrays

An array is a linear collection of values that can be numbers, strings, or objects, stored at contiguous memory indexed locations. Arrays have a fixed number of values of a single data type, making them efficient for both storage and access.

Characteristics:
- Indexed Access: Elements are accessed using their index, providing constant-time complexity 𝑂(1) for retrieval.
- Fixed Size: The size of an array is determined at the time of creation and cannot be changed.
- Homogeneous Elements: Typically store elements of the same type.
- Memory Efficiency: Contiguous memory allocation makes arrays memory efficient.
Common Operations:
- Accessing Elements: 𝑂(1)
- Inserting/Deleting Elements: 𝑂(𝑛) when inserting or deleting in the middle of the array due to the need to shift elements.

Arrays can be used to create subarrays and subsequences, which are subsets of the array that preserve the order of elements.

Hashing

Hashing is a technique used to uniquely identify a specific object from a group of similar objects. It involves converting an input (or key) into a fixed-size string of bytes, usually for faster data retrieval and storage.

Contains Duplicate (Easy) Solution

Understanding the Problem: To understand hash mapping let's take a look at this problem of duplicates. We check if there are any duplicate elements in a numbers array nums. The task find a duplicate at least twice in an array of numbers if there is output true, if not output false.

Let's break down how to solve the NeetCode.io Contains Duplicate: problem. First a brute force and then in TS, an optimal solution with intuition and a step-by-step approach on how to solve the problem.

Pseudocode (Brute Force 💪)

Code

function containsDuplicate(nums):
  if nums empty return false

  // Loop through each element in array
  for i from 0 to nums.length - 1
      // Compare the current element with every other element
      for j from i + 1 to nums.length
          // Check if for duplicate
          if nums[i] === nums[j] return true

  // If not found in the double loop
  return false

Complexity

Time: 𝑂(𝑛^2) nested loops less efficient for large datasets.
Space: 𝑂(1) constant.

TypeScript (Optimal 🎯)

Intuition

To efficiently determine if the nums array has any duplicates, use a hash set a Set is ideal as it only stores unique values and cannot contain duplicates. This method enables us to keep track of elements in constant time, ensuring a quick and efficient check for duplicates. An edge case to consider is if the array is empty, in which case we should return false.

Approach

Check if array is Empty: Return false.
Initialize a Set: Create and empty set to store numbers in the nums array.
Loop Thru Array: Iterate thru each element in array.
Compare for Duplicates:
- If element is in the set return true (duplicate found).
- If element not in set add to set.
Return false: If no delicates are found.

Complexity

Time: 𝑂(𝑛) each element is checked in constant time.
Space: 𝑂(𝑛) all elements are distinct, worst case.

const containsDuplicate = (nums: number[]): boolean => {
  if (nums.length === 0) return false // Array empty

  const set = new Set<number>()

  for (let i = 0; i < nums.length; i++) {
    if (set.has(nums[i])) return true // Duplicate found

    set.add(nums[i])
  }

  return false // No duplicates found
}

// Example usage
const nums: number[] = [1, 2, 3, 1]
console.log(containsDuplicate(nums)) // Output: true

Valid Anagram (Easy) Solution

Understanding the Problem: This NeetCode problem is to determine if two strings are anagrams of each other, we need to ensure that the strings have the same characters with the same frequencies. Let's explore two approaches: a brute force method and a more efficient solution using a hash map.

Let's break down how to solve the NeetCode.io Valid Anagram problem. First a brute force and then in TS, an optimal solution with intuition and a step-by-step approach on how to solve the problem.

Pseudocode (Brute Force 💪)

Code

function validAnagram(s, t):
    if length of s !== t: return false

    /// Sort both strings
    sortedS = sort characters of s
    sortedT = sort characters of t

    // Compare sorted stings
    if sortedS === sortedT:
        return true
    else: return false

TypeScript (Optimal 🎯)

Intuition

Character count approach with hash map avoiding the double sort in the brute force.

Approach

Edge Case Check: If lengths of strings s and t don't match return false.
Character Count Use a hash map to count the frequency of each character in the first string s.

If the character char is already in the charCount object, increment its count.

Validate Against Second String: Iterate thru the second string t

If the character is not in the hash map or it's count is zero return false
decrementing the character count in the hash map.

Final check: Ensure all counts are zero, confirming both strings s and t have the same characters with the same frequency.

Complexity

Time: 𝑂(𝑛), where 𝑛 is the length of the strings.
Space: 𝑂(1), as the hash map size does not depend on the input size (constant space for character set).

const validAnagram = (s: string, t: string): boolean => {
  // Edge case check: if lengths don't match
  if (s.length !== t.length) return false

  // initialize a hash map to count characters in the first string
  const countChar: { [key: string]: number } = {}

  // Loop thru the first string to count each character
  for (let i = 0; i < s.length; i++) {
    const char = s[i]
    // If the character char is already in the countChar object, increment its count for each of the characters
    countChar[char] = (countChar[char] || 0) + 1
  }

  // Loop thru the string to validate characters against the second string
  for (let i = 0; i < t.length; i++) {
    const char = t[i]

    // If the character is not in the hash map or it's count is zero
    if (!countChar[char]) return false

    // Decrement the count for the character
    countChar[char]--
  }

  // Ensure all characters counts are zero, indicating both strings the same characters with the same frequencies
  return Object.values(charCount).every((count) => count === 0)
}

// Example usage
console.log(validAnagram('listen', 'silent')) // Output: true
console.log(validAnagram('hello', 'world')) // Output: false

Two Sum (Easy) Solution

Understanding the Problem: Given an array of integers nums and an integer target, return the indices i and endIdx such that nums[i] + nums[j] === target and i !== j. You can safely assume that every array will have a valid pair of integers that add up to the target. In other words, there will always be at least one solution in the array.

Explanation: Because nums[0] + nums[1] = 9, we return [0, 1]

Let's break down how to solve the NeetCode.io Two Sum problem. First a brute force and then in TS, an optimal solution with intuition and a step-by-step approach on how to solve the problem.

Pseudocode (Brute Force 💪)

Code

function twoSum(nums, target):
    //  Iterate over the array with index i
    for i from 0 to length of nums - 1:
      // Iterate over the array with index j, starting from i + 1 to avoid using the same element twice
       for j from i + 1 to length of nums - 1:
        // Check if the sum of nums[i] and nums[j] equals the target
        if nums[i] + nums[j] === target:
          // If true, return the indices as the solution
          return [i, j]

    // If no solution is found, return an empty list or handle the case as needed
    return []

Using nested loops to check each pair in the array results in a time complexity of 𝑂(𝑛2), which can be inefficient for larger arrays due to the exponential growth in computation time.

TypeScript (Optimal 🎯)

Intuition

Using a hash map to find the complement of each number and to store the nums array of numbers and their indices. Loop through the array, calculating the complement needed to reach the target by subtracting the current element from the target. If the complement is found in the hash map, return the indices of the complement and the current element.

Approach

Initialize Hash map: Create an empty hash map numsMap to store the indices of the nums elements.
Loop Through nums Array:

For each element in the array:
- Calculating the complement by subtracting the current element from the target.
- Check if the complement exists in the hash map.
If it does, return the indices of the complement and the current element.
If it doesn’t, add the current element and its index to the hashmap.

Return the Result: If no such pair is found, return an empty array.

Complexity

Time: 𝑂(𝑛) No nested loops (brute force) in the order of 𝑛, 𝑛 being the number of elements in the array a single pass by leveraging the prefix sum.
Space: 𝑂(𝑛) constant space using a fixed amount of memory.

const twoSum = (nums: number[], target: number): number[] => {
  /// Hash map to store indices
  const numsMap: { [key: number]: number } = {}

  // Iterate thru array for each element in array
  // Calculate it's complement subtracting the element from target
  for (let i = 0; i < nums.length; i++) {
    // Target 9 minus element 2 then complement is 7
    // Target 9 minus next element 7 then complement is 2
    const complement = target - nums[i]

    // Check if complement is already in hash map
    if (numsMap.hasOwnProperty(complement))
      // If the is complement found in the hash map and return it's index (position) and the current number
      return [numsMap[complement], i]

    // If not found add the current element and its index to the hashmap
    numsMap[nums[i]] = i
  }

  // If not found
  return []
}

// Usage
const nums1: number[] = [2, 7, 11, 15]
const target1 = 9 // output [0,1]
const nums2: number[] = [3, 2, 4]
const target2 = 6 // output [1,2]
const nums3: number[] = [3, 3]
const target3 = 6 // output [0,1]

console.log('two sum: ', twoSum(nums1, target1)) // output [0,1]

Group Anagrams (Medium) Solution

Understanding the Problem: We are given an array/list of strings strs, the task is to group **all anagrams** together into sub-lists. Anagrams are strings/words or phrases (not used in this problem) that contain the same characters/letters with the same frequencies. The answer can be returned in **any order**.

Example of anagrams:

"listen" and "silent"
"evil" and "vile"

Let's break down how to solve the NeetCode.io Anagram Groups problem. First a brute force and then in TS, an optimal solution with intuition and a step-by-step approach on how to solve the problem.

Pseudocode (Brute Force 💪)

Code

function groupAnagrams(strs):
  // Initialize an empty object to store the grouped anagrams
  groupedAnagrams = {}

  // Iterate over each value of the input list
  for each string str of strs:
    // Sort the characters of the string to create a key
    key = sort characters of str

    // If the sorted key is not a key in the object, add it with an empty array/list
    if key not in groupedAnagrams:
      groupedAnagrams[key] = [] // an empty list for this key

    // Add the original string into the corresponding sorted key list
    add str to the list corresponding to key in groupedAnagrams

  // Return the grouped anagrams as a list of lists
  return values of groupedAnagrams

Complexity

Time: 𝑂(𝑛 ⋅ 𝑘 log 𝑘) 𝑛 number of strings in the input list 𝑘 is the length of the string. Since we need to sort each string in the input list of 𝑛 strings.
Space: 𝑂(𝑛 ⋅ 𝑘) 𝑛 strings with an average length of 𝑘.

TypeScript (Optimal 🎯)

Intuition

We start with creating an object to store the group anagrams as a reference. We then loop thru the strs array to create a new Array to count the frequency of each character. Using ASCII code and an inner loop to count the frequency of each character in the string (for example with the charCodeAt() method indexing characters from 'a' to 'z' where 'a' is indexed at 0 and 'z' at 25) and then for each character in the string increment the count array by 1. Making this more optimal as character frequency counts instead of sorting in the brute force. We then create a key from the character count, and if it's not in the groupedAnagrams object, initialize it with an empty array. Then we add the key original string to the key. Finally, we return the values in the groupedAnagrams object as a list of lists.

Approach

Initialize: An empty storage object groupedAnagrams to store the grouped anagrams.
Character Frequency Counting: For each string, count the frequency of each character to form a key with 26 slots (one for each letter of the alphabet) is used to count how many times each letter appears in the string.
Create a Key: Convert the count array into a string key.
Check Key Existence: If the key is not in the dictionary, initialize it with an empty array.
Group Anagrams: Append the original string str to the array for the corresponding key.
Return Grouped Anagrams: Return the grouped anagrams as an list of lists using Object.values(groupedAnagrams).

Complexity

Time: 𝑂(𝑛 ⋅ 𝑘) where 𝑛 is the number of strings and 𝑘 is the average length of the strings.
Space: 𝑂(𝑛 ⋅ 𝑘) for storing 𝑛 strings in the dictionary.

const groupAnagrams = (strs: string[]): string[][] => {
  // Initialize an empty object to store the grouped anagrams
  const groupedAnagrams: { [key: string]: string[] } = {}

  // Iterate over each string in the input list
  for (let str of strs) {
    // Initialize an array to count the frequency of each character
    const count: number[] = new Array(26).fill(0)

    // Count the frequency of each character
    for (let char of str) {
      // ASCII code for 'a' is 97
      count[char.charCodeAt(0) - 'a'.charCodeAt(0)] += 1
    }

    // Create a key to convert the character count array into a string key
    const key = count.join(',')

    // If the key is not yet in the object, add it with an empty array
    if (!groupedAnagrams[key]) {
      groupedAnagrams[key] = []
    }

    // Add the original string into the corresponding group
    groupedAnagrams[key].push(str)
  }

  // Return the grouped anagrams as an array of arrays
  return Object.values(groupedAnagrams)
}

// Example Usage
const strs = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
console.log(groupAnagrams(strs)) // Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Top ‘𝐾’ Frequent Elements (Medium) Solution

Understanding the Problem: Given an integer array of nums and an integer k return the k most frequent elements within the array. The order of the result doesn't matter.

Example 1:

Example 2:

Input: nums = [1], k = 1

Output: [1]

Let's break down how to solve the NeetCode.io Top K Frequent Elements problem. First a brute force and then in TS, an optimal solution with intuition and a step-by-step approach on how to solve the problem.

Pseudocode (Brute Force 💪)

Code

function topKFrequent(nums, k):
  // Create an object to count the frequency of each number
  freqCount = {}

  // Count the frequency of each number
  for each num of nums:
  // If 'num' is not in 'countFreq', initialize to 0 and then increment by 1;
  // if it exists, just increment by 1
  countFreq[num] = (countFreq[num] || 0) + 1

  // Convert frequency object to array and sort by frequency
  countArr = entries of freqCount sort countArr by second element in descending order

  // Create an array to store top K elements
  topK = []
  // Extract the top K element
  for i from 0 to k - 1
    // Append first item in the pair (the number) to the topK array
    append countArr[i][0] to topK

  // Return the array containing the top K elements
  return topK

Input: nums = [2, 4, 4, 6, 6, 6] k = 2

Output: [6, 4] as 6 appears three times and 4 appears two times.

Complexity

Time: 𝑂(𝑛 + 𝑚 log 𝑚)
- Counting the freq of each element takes 𝑂(𝑛) where 𝑛 is the total number of elements in nums and 𝑚 is the number of unique elements.
- Sorting the unique elements takes 𝑂(𝑚 log 𝑚).
Space: 𝑂(𝑚 + 𝑘)
- ThecountMap uses 𝑂(𝑚) space to store the frequency of each unique element.
- The countArray uses 𝑂(𝑚) space when sorting the elements.
- The result array topK uses 𝑂(𝑘) space, where 𝑘 is the top freq elements returned.

TypeScript (Optimal 🎯)

Intuition

The goal is to identify the elements that appear most frequently. We can achieve this is by counting the frequency of each element using a hash map and then selecting the k elements with the highest counts. To efficiently keep track these elements, we use a heap (priority queue) to store the k most frequent elements.

Approach

Initialize Hash Map: A Map countMap is used to count of the frequency of each number in the nums array.
Loop thru nums: For each number in the nums array, update the count in the countMap.
Min-Heap Creation:

An array heap is used to simulate a min-heap (priority queue).

Loop thru countMap:

For each entry in the countMap, add the [count, num] pair to the heap.
- If the heap size exceeds k sort the heap to ensure the smallest count is at the top the remove the smallest element to maintain the heap's size.

Extract Top K Elements:

Return the numbers topK from the heap using the map method to retrieve and return the top k elements.

Complexity

Time: 𝑂(𝑛 + 𝑚 log 𝑚)
- Counting the frequency of each element takes 𝑂(𝑛) time, where 𝑛 is the total number of elements in nums and 𝑚 is the number of unique elements.
- Sorting the unique elements takes 𝑂(𝑚 log 𝑚) time.
Space: 𝑂(𝑚 + 𝑘)
- The countArray uses 𝑂(𝑚) to store the frequency of each unique element.
- The countArray uses 𝑂(𝑚) space when sorting the elements.
- The result array topK uses 𝑂(𝑘) space, where 𝑘 is the top freq elements returned.

function topKFrequent(nums: number[], k: number) {
  // Create a hash map to count the frequency of each number
  const countMap = new Map<number, number>()

  // Count the frequency of each number
  for (const num of nums) {
    // Check if it's not in the countMap not yet in the map (count is undefined),
    // it defaults to 0
    countMap.set(num, (countMap.get(num) || 0) + 1)
  }

  // Create a min-heap to store the top  K elements
  const heap: [number, number][] = []

  // Populate the heap with pairs from the countMap
  for (let [num, count] of countMap) {
    // Append the [count, num] pair to the heap
    heap.push([count, num])
    // If the heap size exceeds K, remove the smallest element
    if (heap.length > k) {
      heap.sort((a, b) => a[0] - b[0]) // Keep the smallest element at the top
      heap.shift() // Remove the element with the smallest count
    }
  }

  // Create array and populate with extracted top K elements
  const topK = heap.map((entry) => entry[1])

  return topK
}

const numbers: number[] = [2, 2, 2, 4, 4, 6]
const k: number = 2

console.log(topKFrequent(numbers, k)) // Array [ 2, 4 ]

Encode and Decode Strings (Medium)

Understanding the Problem: Design an algorithm to encode a list of strings to a single string. The encoded string is (sent over the network) then decoded back to the original list of strings.

Implement encode and decode.

Let's break down how to solve the NeetCode.io Encode and Decode Strings problem. First a brute force and then in TS, an optimal solution with intuition and a step-by-step approach on how to solve the problem.

Pseudocode (Brute Force 💪)

Code

function encode(strs):
  encodedStr = ""

  // Iterate thru strings
  for each str of strs:
    // Escape colons in the string
    escapedStr = str.replace(/:/g, "::")
    // Append the length of the escaped string to the encodedStr
    encodedStr += length(escapedStr) + ":" + escapedStr

  // Return the encoded string
  return encodedStr

function decode(encodedStr):
  // List to store decoded strings
  decodedStrs = []
  // Initialize index
  idx = 0

  // Loop thru the encoded string
  while idx < length(encodedStr):
    // Find the index of the delimiter
    delimiterIdx = encodedStr.indexOf(":", idx)
    // Get the length of the string
    strLength = parseInt(encodedStr substring from idx to delimiterIdx)
    // Move the index after the delimiter
    idx = delimiterIdx + 1
    // Extract substring from idx up to (but not including) idx + str_length
    escapedStr = encodedStr.substring(idx, idx + strLength)
    // Replace double colons with single colons
    decodedStr = escapedStr.replace(/::/g, ":")
    // Add the decoded string to the list
    append decodedStr to decodedStrs

    // Move the index forward by the strLength
    idx += strLength

  // Return decode strings
  return decodedStrs

TypeScript (Optimal 🎯)

Intuition

Using a special character as a delimiter (e.g., :) might not be reliable because the character could already exist in one of the strings (e.g., strs = ["we", "say", ":", "yes"]). Instead, a more robust approach is to store the length of each string before the delimiter, this ensures accurate decoding without conflicts.

Since the array cannot store additional metadata about individual strings such as lengths this approach efficiently encodes the necessary information within a single string.

Approach

Encode Function:

Initialize Encoded String:

Create an empty string encodedStr to store the encoded string result.

Loop Through Each String in the Input Array:

For each string in the array:
- Calculate the length of the string.
- Append the length of the string plus a delimiter (#) and then the actual string to encodedStr.

Return encodedStr:

The function returns the final encoded string, which represents all strings in a compact form, concatenated encodedStr string.

The encoded string encodedStr = "4#neet4#code4#love3#you" can be decoded efficiently by parsing the length before each #.

Decode Function:

Initialize:

An empty array decodedStrs to store the decoded strings.
An index idx to track of the current position in the encoded string.

Loop Through the Encoded String:

While idx is less than the length of the encodedStr:
- Initialize endIdx to idx to locate the delimiter #.

Locate the Delimiter #:

Increment endInx until encodedStr[endIdx] === "#" which marks the end of the string length.

Extract the String:

Convert the substring using parseInt from idx to endIdx into an integer strLength.
Move idx past the delimiter (idx = endIdx + 1).
Then extracting the actual string using strLength (encodedStr.substring(idx, idx + strLength)).
Update idx – Move index to the next encoded segment.
Append the decoded string to the list.

Return decodedStrs:

Return the array decodedStrs which contains all decoded strings.

Encoding example: For strs = ["neet", "code", "love", "you"] the encoding and decoding process:

Index	Encoded Format	Extracted Length	Extracted String	decodedStrs
0	`"4#neet"`	4	"neet"	["neet"]
6	`"4#code"`	4	"code"	["neet", "code"]
12	`"4#love"`	4	"love"	["neet", "code", "love"]
18	`"3#you"`	3	"you"	["neet", "code", "love", "you"]

The decode function converts the string "4#neet4#code4#love3#you" back into the array ["neet", "code", "love", "you"].

Complexity

Time: 𝑂(𝑛) each character in the encoded string is processed once.
Space: 𝑂(𝑛) the the decoded strings are stored in an array of size n.

function encode(strs: string[]): string {
  let encodedStr: string = ''

  // Iterate over each string in the array
  for (const str of strs) {
    // Append the length of the string, a delimiter '#',
    // and the actual string
    encodedStr += str.length + '#' + str
  }

  return encodedStr
}

function decode(encodedStr: string): string[] {
  const decodedStrs: string[] = []
  let idx: number = 0

  while (idx < encodedStr.length) {
    // Pointer to find the delimiter '#'
    let endIdx: number = idx

    // Locate the position of the delimiter '#'
    while (encodedStr[endIdx] !== '#') {
      endIdx++
    }

    // Extract the length of the next string
    const strLength: number = parseInt(encodedStr.substring(idx, endIdx))

    // Move index past the delimiter to the start of the actual string
    idx = endIdx + 1

    // Extract the string using the parsed length
    endIdx = idx + strLength
    // Append the decoded string to the list
    decodedStrs.push(encodedStr.substring(idx, endIdx))

    // Move index to the next encoded segment
    idx = endIdx
  }

  return decodedStrs
}

Input: `strs` = ['neet', 'code', 'love', 'you']
Encode: `encodedStr` = '4#neet4#code4#love3#you'
Decode: `decodedStrs` = ['neet', 'code', 'love', 'you']

Product of Array Except Self (Medium)

Understanding the Problem: Given an integer array nums, the task is to return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

Each product is guaranteed to fit in a 32-bit integer.

The output array should not use division and should have a time complexity of O(n).

Let's break down how to solve the NeetCodeIO Products of Array Except Self problem. First a brute force and then in TS, an optimal solution with intuition and a step-by-step approach on how to solve the problem.

Pseudocode (Brute Force 💪)

Code

function productExceptSelf(nums):
  // Initialize an array to store the products
  products = []

  // Loop through each element in the array
  for i from 0 to length of nums - 1:
    // Initialize the product
    product = 1
    // Loop through each element in the array
    for j from 0 to length of nums - 1:
      // Skip the current element
      if i !== j:
        // Multiply the product by the current element
        product *= nums[j]
    // Add the product to the products array
    append product to products

  // Return the products array
  return products

Complexity

Time: 𝑂(𝑛^2) nested loops less efficient for large datasets.
Space: 𝑂(𝑛) constant.

TypeScript (Optimal 🎯)

Intuition

The goal is to find the product of all elements in the array except the current element. We can achieve this by calculating the product of all elements to the left and right of the current element.

Approach

Initialize Arrays: Create two arrays leftArr and rightArr to store the products of all elements to the left and right of the current element.
Calculate Left Products:

Initialize the leftArr array with the product of all elements to the left of the current element.
Iterate through the array from left to right, multiplying the current element by the previous element.

Calculate Right Products:

Initialize the rightArr array with the product of all elements to the right of the current element.
Iterate through the array from right to left, multiplying the current element by the previous element.

Calculate Final Products:

Initialize an empty array products to store the final products.
Multiply the leftArr and rightArr arrays to get the final product of all elements except the current element.

Return Products: Return the products array containing the final products.

Complexity

Time: 𝑂(𝑛) for both the left and right products.
Space: 𝑂(𝑛) for the left and right arrays and the final products array.

function productExceptSelf(nums: number[]): number[] {
  // Store the length of the input array
  const numsLength: number = nums.length
  // Create arrays to store cumulative products of elements to the left and right of each index
  const leftArr: number[] = new Array(numsLength).fill(1)
  const rightArr: number[] = new Array(numsLength).fill(1)
  const products: number[] = new Array(numsLength).fill(1) // Final output array

  // Populate leftArr: leftArr[i] contains the product of
  // all elements to the left of index i
  for (let i = 1; i < numsLength; i++) {
    leftArr[i] = leftArr[i - 1] * nums[i - 1]
  }

  // Populate rightArr: rightArr[i] contains the product of
  // all elements to the left of index i
  for (let i = numsLength - 2; i >= 0; i--) {
    rightArr[i] = rightArr[i + 1] * nums[i + 1]
  }

  // Compute the final product array: product at index i is
  // leftArr[i] * rightArr[i]
  for (let i = 0; i < numsLength; i++) {
    products[i] = leftArr[i] * rightArr[i]
  }

  return products
}

DSA Arrays Hashing TypeScript

Introduction

Why Arrays and Hashing?

Arrays

Hashing

Contains Duplicate (Easy) Solution

Pseudocode (Brute Force 💪)

Complexity

TypeScript (Optimal 🎯)

Intuition

Approach

Complexity

Valid Anagram (Easy) Solution

Pseudocode (Brute Force 💪)

TypeScript (Optimal 🎯)

Intuition

Approach

Complexity

Two Sum (Easy) Solution

Pseudocode (Brute Force 💪)

TypeScript (Optimal 🎯)

Intuition

Approach

Complexity

Group Anagrams (Medium) Solution

Pseudocode (Brute Force 💪)

Complexity

TypeScript (Optimal 🎯)

Intuition

Approach

Complexity

Top ‘𝐾’ Frequent Elements (Medium) Solution

Pseudocode (Brute Force 💪)

Complexity

TypeScript (Optimal 🎯)

Intuition

Approach

Complexity

Encode and Decode Strings (Medium)

Pseudocode (Brute Force 💪)

TypeScript (Optimal 🎯)

Intuition

Approach

Complexity

Product of Array Except Self (Medium)

Pseudocode (Brute Force 💪)

Complexity

TypeScript (Optimal 🎯)

Intuition

Approach

Complexity

Todo

Valid Sudoku (Medium)

Todo

Reference