12. Arrays & Hashing

A. General Introduction

B. Leetcode problems

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

Example:

Input: nums = [100,4,200,1,3,2]
Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Key ideas:

• What determines a sequence is the start and end, so create a set and check if the num-1 exists in the set
  • If it does not exist, then it is the start of a sequence
    • iteratively increase the length of the sequence till the num is not in the set
    • check max length

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:

        if not nums:
            return 0

        history = set(nums)
        maxlen = float("-inf")

        for num in nums:

            if num-1 not in history:
                # start of a sequence
                length = 0
                while (num+length) in history:
                    length += 1

                maxlen = max(maxlen, length)

        return maxlen

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

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Key Ideas:

• Use a hash table to store the number and its index
• Iterate through the array and check if the number is in the hash table
  • If it is, return the index pair
  • If it is not, then add the difference between the number and target to the hash table with the index

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

        hashmap = {}

        for i, val in enumerate(nums):

            if val in hashmap:
                return [hashmap[val], i]

            hashmap[target-val] = i

        return -1