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 & 🔓 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 through Array: Iterate through 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
    return sortedS === sortedT

This approach is simple and effective. It has a time complexity of 𝑂(𝑛 log 𝑛) due to the sorting step, where n is the length of the strings.

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 through 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.

Optional final verification: ensure all counts are zero, confirming both strings have identical character frequencies

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 => {
    // Early exit: strings of different lengths cannot be anagrams
    if (s.length !== t.length) return false

    // Hash map to track character counts in the first string
    const countChar: { [key: string]: number } = {}

    // Count the frequency of each char in the first string
    for (let i = 0; i < s.length; i++) {
        const char = s[i]
        // Increment the count for this character, initializing it to 0 if it not present
        countChar[char] = (countChar[char] || 0) + 1
    }

    // Validate the second string against the hash map
    for (let i = 0; i < t.length; i++) {
        const char = t[i]

        // If char doesn't exist in the hash map or its count is zero, return false it means not an anagram
        if (!countChar[char]) return false

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

    // Optional final check to ensure all counts are zero
    return Object.values(countChar).every((count) => count === 0)
}

// Example usage
console.log(validAnagram('listen', 'silent')) // true
console.log(validAnagram('hello', 'world')) // 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

Use a hash map to quickly find the complement of each number (the value needed to reach the target).

As you loop through the array:

For each number, calculate complement = target - current number.
If that complement has already been seen (stored in the map), you found the pair—return their indices.
Otherwise, store the current number and its index in the map for future reference.

This way, you only need to traverse the array once, achieving a time complexity of 𝑂(𝑛).

Approach

Initialize a hash map: numsMap to store { number: index } pairs.
Iterate through the nums Array:

For each element in the array:
- Compute the complement by subtracting the current element from the target complement = target - nums[i].
- If the complement exists in the hashmap, return the indices of the complement and the current element [numsMap[complement], i].
- Otherwise, store the current number and its index in the hashmap numsMap[nums[i]] = i.

If no such pair is found, return an empty array.

Complexity

Time: 𝑂(𝑛) each lookup and insertion in the hash map is constant time, and we only pass through the array once.
Space: 𝑂(𝑛) we store at most one entry per element in the array.

const twoSum = (nums: number[], target: number): number[] => {
    /// Hash map to store number → index
    const numsMap = new Map<number, number>()

    // Loop through each number in the array
    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 stored in the 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]

        // Store the current number and its index in the hash map
        numsMap[nums[i]] = i
    }

    // Return empty if no pair sums to target
    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):
  // Create an empty map to store the grouped anagrams
  groupedAnagrams = {}

  // Loop through each string in the input list
  for each string str of strs:
    // Generate a key by sorting the characters in the string
    key = sort characters of str and join into a string

    // If this key is not in the map, initialize it with an empty list
    if key not in groupedAnagrams:
      groupedAnagrams[key] = []

    // Add the string to the group corresponding to this key
    add str to the list corresponding to key in groupedAnagrams

  // Return all grouped anagrams lists of anagrams
  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 use a hash map to group words that are anagrams. Instead of sorting each string (which costs 𝑂(𝑘 log 𝑘) time per word), we build a 26-length frequency array for each string, counting how many times each character appears.

This gives us an 𝑂(𝑘) signature, which we convert into a string key.

Words with the same character counts will generate the same key, allowing us to group them efficiently.

Finally, we return all grouped anagram lists using Object.values(groupedAnagrams).

Approach

Initialize: Create an empty hash map (a plain object) called groupedAnagrams where each key is a character-frequency signature and each value is a list of words belonging to that group.
Count Characters: For each string, create a count array of size 26 zeros. As you iterate through the characters, update the corresponding index based on the letter (a → 0, b → 1, ..., z → 25) using its ASCII code.
Create a Key: Convert the count array into a string (e.g., "1,0,0,0,1,0,...") so it can be used as a hash map key.
Store the Word: If the key doesn't exist in groupedAnagrams, initialize it with an empty array. Then push the current word into the appropriate group.
Return Result: After processing all the strings, return the grouped anagrams 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)]++
        }

        // 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 nums and an integer k return the k most frequent elements in nums. The order of the returned elements does not 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 💪)

Sorting Approach

Code

function topKFrequent(nums, k):
    // 1. Count the frequency of each element using a hash map
    freqCount = {}

    // Build frequency table
    for each num of nums:
        freqCount[num] = (freqCount[num] || 0) + 1

    // 2. Convert the frequency map to an array of [num, count] pairs
    // and sort by frequency in descending order
    countArr = entries(freqCount) sort by second element DESC

    // 3. Collect the first k numbers (highest frequency)
    topK = []

    // 4. Extract the top k elements from the sorted array
    for i from 0 to k - 1
        append countArr[i][0] to topK

    // 5. Return the top k frequent numbers
    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: 𝑂(𝑚 + 𝑘)
- The countMap 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 Min-Heap

Intuition

We want the k most frequent values from the nums array. Instead of sorting all unique elements 𝑂(𝑚 log 𝑚), we can use a min-heap (priority queue) of size k to efficiently keep track of the top k frequent elements that currently have the highest frequency. The min-heap always ensures the element with the lowest count among the top k is at the root, ready to be removed if a new, more frequent element is encountered.

Approach

Count Frequencies: Use a Map as a hash map countMap to count the many times each number appears in the nums array.
Populate the countMap: For each number, increment its count in the countMap.
Min-Heap Creation:

Instantiate a MinPriorityQueue<{ num: number; count: number }> (min-heap /priority queue) that is prioritized by the count of the element.

Loop through countMap:
- For each [num, count] entry, enqueue the element with the smallest count (the root of the min-heap) to maintain only the top k frequent elements.
Extract Top K Elements:

Dequeue all remaining elements from the min-heap, extract their num property, and store them in an array (topK).
Reverse the final result, as dequeuing from min-heap gives elements in ascending order of frequency (which is what we want to reverse to get the descending order)

Complexity

Time: 𝑂(𝑛 + 𝑚 log 𝑘)
- 𝑂(𝑛 for iterating through nums array and counting into the countMap, where 𝑛 is the length of nums.
- 𝑂(𝑚 log 𝑘) for inserting 𝑚 unique elements into a heap of size 𝑘, as each insertion/removal takes 𝑂(log 𝑘) time.
Space: 𝑂(𝑚 + 𝑘)
- The countMap uses 𝑂(𝑚) space to store the frequency of each unique element.
- The min-heap uses 𝑂(𝑘) space to store the top k frequent elements.

function topKFrequent(nums: number[], k: number): number[] {
    // 1. Map to count how many times each number appears in the nums array
    const countMap = new Map<number, number>()

    // 2. Add [num, count] pairs to the countMap
    for (const num of nums) {
        countMap.set(num, (countMap.get(num) || 0) + 1)
    }

    // Min-heap stores [count, num] pairs
    const heap = new MinPriorityQueue<{ num: number; count: number }>(
        (entry) => entry.count // Min-heap based on count
    )

    for (const [num, count] of countMap) {
        heap.enqueue({ num, count })

        // Keep the heap size to k by removing the smallest count
        if (heap.size() > k) heap.dequeue()
    }

    // 3. Extract just the numbers from the heap
    const topK = []
    while (heap.size() > 0) {
        topK.push(heap.dequeue().num)
    }

    return topK.reverse()
}

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

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

TypeScript Bucket Sort (Optimal 🎯)

Intuition

We can use a bucket sort approach to efficiently find the top k frequent elements. The idea is to create an array of buckets where the index represents the frequency of elements. Each bucket at index i will contain a list of numbers that appear i times in the input array.

Approach

Count Frequencies: Use a Map to count the frequency of each number in the nums array.
Create Buckets: Create an array of empty arrays (buckets) where the index represents the frequency. The size of this array will be nums.length + 1 since the maximum frequency of any number can be nums.length.
Populate Buckets: For each number and its frequency in the frequency map, add the number to the corresponding bucket based on its frequency.
Collect Top K Elements: Iterate through the buckets in reverse order (from highest frequency to lowest) and collect numbers until we have k elements.

Complexity

Time: 𝑂(𝑛) where 𝑛 is the length of the nums array. Counting frequencies takes 𝑂(𝑛), populating buckets also takes 𝑂(𝑛), and collecting top k elements takes at most 𝑂(𝑛).
Space: 𝑂(𝑛) for the frequency map and the buckets.

function topKFrequent(nums: number[], k: number): number[] {
    const countMap = new Map<number, number>()

    // Count the frequency of each number
    for (const num of nums) {
        countMap.set(num, (countMap.get(num) || 0) + 1)
    }

    // Create buckets where index represents frequency
    const buckets: number[][] = Array.from(
        { length: nums.length + 1 },
        () => []
    )

    // Populate the buckets
    for (const [num, count] of countMap) {
        buckets[count].push(num)
    }

    const topK: number[] = []

    // Collect top k frequent elements from the buckets
    for (let freq = buckets.length - 1; freq >= 0 && topK.length < k; freq--) {
        for (const num of buckets[freq]) {
            topK.push(num)
            if (topK.length === k) break
        }
    }

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

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

🔐 Encode & 🔓 Decode Strings (Medium)

Understanding the Problem:

This solution walks through a classic interview problem: converting an array of strings into a single encoded string, and decoding it back.

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 through 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 through 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 + strLength
    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.

This is done by prepending the length of each string followed by a delimiter (e.g., #) to the string itself. For example, the string "neet" would be encoded as "4#neet", where 4 is the length of the string and # is the delimiter. This allows us to easily parse the encoded string to retrieve the original strings without worrying about special characters or delimiters.

Encoding: The process of converting a list of strings into a single string.
Decoding: The process of converting the encoded string back into the original list of strings.
Delimiter: A special character used to separate the encoded strings in the final string.
Escape: The process of replacing special characters in the string to avoid conflicts with delimiters.

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 it's length.
- Append the length a delimiter (#) and the actual string to encodedStr.

Return:

Return the encodedStr which contains all encoded strings in the format <length>#<string>.

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.

While Loop:

While idx is less than the length of the encodedStr:
- Use a pointer endIdx to find the delimiter # in the encoded string.
- Increment endIdx until encodedStr[endIdx] === "#".
- This marks the end of the string length.

Extract the String:

Extract the substring using slice from idx to endIdx and convert it to an integer strLength.
Move idx past the delimiter (i.e., idx = endIdx + 1).
Extract the actual string using strLength (encodedStr.slice(idx, idx + strLength)).
Append the decoded string to the list decodedStrs.
Update idx to the next encoded segment's start by adding strLength to idx.
Repeat until all strings are decoded

Return decodedStrs:

Return the array decodedStrs which contains all decoded strings.

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

Step	Idx	endIdx	Encoded Format	slice(idx, endIdx)	Extracted Length	Extracted String	decodedStrs
1	0	1	`"4#neet"`	"4"	4	"neet"	["neet"]
2	6	7	`"4#code"`	"4"	4	"code"	["neet", "code"]
3	12	13	`"4#love"`	"4"	4	"love"	["neet", "code", "love"]
4	18	19	`"3#you"`	"3"	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.

/**
 * Encodes an array of strings to a single string.
 * Format: "<length>#<string>"
 * @param {string[]} strs - Array of strings to encode
 * @returns {string}
 */
function encode(strs: string[]): string {
    let encodedStr: string = ''

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

    return encodedStr
}

/**
 * Decodes a single string back into an array of strings.
 * @param encodedStr - The encoded string
 * @returns Array of decoded strings
 */

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++ // Increment until '#' is found

        // Extract the length of the string
        // Convert the substring to an integer
        const strLength: number = parseInt(encodedStr.slice(idx, endIdx))

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

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

        // Move the index forward by the length of the string to the next encoded segment
        idx += strLength
    }

    return decodedStrs
}

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

function testCodec(): void {
    const strs = ['neet', 'code', 'love', 'you']
    const encodedStr = encode(strs)
    const decodedStrs = decode(encodedStr)

    console.log('Original:', strs)
    console.log('Encoded :', encodedStr)
    console.log('Decoded :', decodedStrs)

    const isEqual = JSON.stringify(strs) === JSON.stringify(decodedStrs)
    console.assert(
        isEqual,
        '❌ Test failed: Decoded output does not match the original'
    )
    if (isEqual) {
        console.log('✅ Test passed!')
    }
}

testCodec()

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 💪)

Sorting Approach

Complexity

TypeScript Min-Heap

Intuition

Approach

Complexity

TypeScript Bucket Sort (Optimal 🎯)

Intuition

Approach

Complexity

🔐 Encode & 🔓 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