Array & Hashing - LeetCode Problems

Some leetcode problems relate to array and hashing.

Github: LeetCode-Solutions by Mitchell

---

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Solutions

Using a set to filter the duplicate elements and compare the size of the set to the length of the original array.

Complexity:

• Time: O(1)

• Space: O(n)

Code

TypeScript

const containsDuplicate = function(nums: number[]): boolean {
  const numSet: Set<number> = new Set(nums);
  
  return numSet.size !== nums.length;
}

Python

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashset = set(nums)
        
        return len(hashset) != len(nums)

Relate ideas

• In computer science, a set is an abstract data type that can store unique values, without any particular order. - Wikipedia.org

---

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Solutions

Using a cyclic sort technique to identify the duplicate by swapping elements to their correct positions until a duplicate is found.

Complexity:

• Time: O(n)

• Space: O(1)

Code

TypeScript

const findDuplicate = function(nums: number[], start: number = 0): number {
  const swap = (arr: number[], a: number, b: number): [number, number] => [arr[a], arr[b]] = [arr[b], arr[a]];

  const isSame = (): boolean => nums[start] === nums[nums[start]];
  while (!isSame()) {
    swap(nums, start, nums[start]);
  } 

  return nums[start];
}

Python

class Solution:
    def findDuplicate(self, nums: List[int], start: int = 0) -> int:
      def swap(arr: List[int], a: int, b: int) -> None:
        arr[a], arr[b] = arr[b], arr[a]
      
      def is_same() -> bool:
        return nums[start] == nums[nums[start]]

      while not is_same():
        swap(nums, start, nums[start])
      
      return nums[start]

Relate ideas

• Cycle sort is an in-place, unstable sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result. - Wikipedia.org

---

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Solutions

Using a hash map to keep track of the numbers and their indices.

Complexity:

• Time: O(n)

• Space: O(n)

Code

TypeScript

const twoSum = function(nums: number[], target: number): number[] {
  const hashmap: { [key: number]: number } = {};

  for (const [index, element] of nums.entries()) {
    const complement = target - element;
    if (complement in hashmap) {
      return [index, hashmap[complement]];
    }

    hashmap[element] = index;
  }
}

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}

        for idx, ele in enumerate(nums):
          complement = target - ele
          if (complement in hashmap):
              return [idx, hashmap[complement]]
          hashmap[ele] = idx	

Relate ideas

• In computing, a hash table is a data structure that implements an associative array, also called a dictionary or simply map, which is an abstract data type that maps keys to values. - Wikipedia.org

---

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Solutions

Leveraging a hash map for frequency counting and sorting for selecting the most frequent elements.

Complexity:

• Time: O(nlogn)

• Space: O(n)

Code

TypeScript

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

  for (const num of nums) {
    if (hashmap.has(num)) {
      hashmap.set(num, hashmap.get(num) + 1);
    } else {
      hashmap.set(num, 1);
    }
  }

  const arr: number[][] = Array.from(hashmap).sort((a, b) => b[1] - a[1]);

  for (let i = 0; i < k; i++) {
    result.push(arr[i][0]);
  }

  return result;   
}

Python

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count_map = {}
        freq_list = [[] for i in range(len(nums)+1)]

        for num in nums:
            count_map[num] = count_map.get(num, 0) + 1
        
        for element, freq in count_map.items():
            freq_list[freq].append(element)
        
        res = []

        for i in range(len(freq_list)-1, 0, -1):
            for sub in freq_list[i]:
                res.append(sub)
                if len(res) == k:
                    return res

---

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Solutions

Leveraging a min-heap to maintain the k largest elements in the array.

Complexity:

• Time: O(nlogk)

• Space: O(k)

Code

TypeScript

const findKthLargest = function(nums: number[], k: number): number {
  const minHeap = new MinPriorityQueue();  

  for (const num of nums) {
    minHeap.enqueue(num);
    if (k < minHeap.size()) {
      minHeap.dequeue();
    }
  } 

  return minHeap.front().element;
}

Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[len(nums) - k]

Relate ideas

• In computer science, a heap is a tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node. - Wikipedia.org

---

Product of Array Except Self

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

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Solutions

Initializes a result array with ones, then iterates twice over the input array to multiply each element by the accumulated product of all previous (prefix) and following (postfix) elements, returning the final result array.

Complexity:

• Time: O(n)

• Space: O(n)

Code

TypeScript

const productExceptSelf = function(nums: number[]): number[] {
  const result: number[] = new Array(nums.length).fill(1);
  let [prefix, postfix]: [number, number] = [1, 1]; 

  for (let i = 0; i < nums.length; i++) {
    result[i] = prefix;
    prefix *= nums[i];
  } 

  for (let i = nums.length-1; i >= 0; i--) {
    result[i] *= postfix;
    postfix *= nums[i];
  }
  
  return result;
}

Python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * len(nums)
        prefix, postfix = 1, 1

        for i in range(len(nums)):
            res[i] = prefix
            prefix *= nums[i]

        for i in range(len(nums)-1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]
        
        return res

---

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solutions

Using a hash set to store all elements, then for each element not preceded by another, count consecutive numbers starting from it, updating the maximum length found.

Complexity:

• Time: O(n)

• Space: O(n)

Code

TypeScript

const longestConsecutive = function(nums: number[]): number {
  const hashset: Set<number> = new Set(nums);
  let longest: number = 0;

  for (const element of hashset) {
    if (!hashset.has(element-1)) {
      let length = 1;
      while (hashset.has(element+length)) {
        length += 1;
      }
      longest = Math.max(length, longest);
    }
  }

  return longest;
}

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hashset = set(nums)
        longest = 0

        for num in hashset:
            if num-1 not in hashset:
                length = 1
                while num+length in hashset:
                    length += 1
                longest = max(longest, length)
        
        return longest

---

References

• LeetCode 217.Contains Duplicate

• Set (abstract data type)

• LeetCode 287. Find the Duplicate Number

• Cycle sort

• LeetCode 1. Two Sum

• Hash table

• LeetCode 347. Top K Frequent Elements

• LeetCode 215. Kth Largest Element in an Array

• Heap (data structure)

• LeetCode 238. Product of Array Except Self

• LeetCode 128. Longest Consecutive Sequence

• NeetCode