Array & hasing

Two Sum - Easy

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Example 1:

Input: nums = [3,4,5,6], target = 7
Output: [0,1]

Example 2:

Input: nums = [4,5,6], target = 10
Output: [0,2]

For each number, look up its difference (target − num) in the map; if missing, store the number→index and move on.

Approach: Hash Map

Time: O(n)

Space: O(n)

Contain Duplicate - Easy

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Example 1:

Input: nums = [1, 2, 3, 3]
Output: true

Example 2:

Input: nums = [1, 2, 3, 4]
Output: false

Add numbers to a set one by one; if one's already there, it's a duplicate.

Approach: Hash Set

Time: O(n)

Space: O(n)

Valid Anagram - Easy

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

Two strings are anagrams if they contain the same characters, with each character appearing the same number of times, regardless of order.

Example 1:

Input: s = "racecar", t = "carrace"
Output: true

Example 2:

Input: s = "jar", t = "jam"
Output: false

Example 3:

Input: s = "x", t = "x"
Output: true

Count characters in both strings; they're anagrams if the two count maps match

Approach: Hash Map

Time: O(n)

Space: O(1) at most 26 lowercase letters

Group Anagram - Medium

Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

Input: strs = ["act","pots","tops","cat","stop","hat"]
Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]

Example 2:

Input: strs = ["x"]
Output: [["x"]]

Bucket words in a map keyed by their sorted letter (or 26-letter count)

Approach: Hash Table for Character Count

Time: O(m * n)

Space: O(m * n)

Where m is the number of strings and n is the length of the longest string

Top K Frequent Elements - Medium

Given an integer array nums and an integer k, return the k most frequent elements within the array.

The test cases are generated such that the answer is always unique.

You may return the output in any order.

Example 1:

Input: nums = [1,2,2,3,3,3], k = 2
Output: [2,3]

Example 2:

Input: nums = [7,7], k = 1
Output: [7]

Count frequencies, then bucket sort by frequency and take the top k

Approach: Bucket Sort

Time: O(n)

Space: O(n)

Encode and Decode Strings - Medium

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Prefix each string with its "length#", then decode by reading the length before each string

Approach: length#string per entry

Time: O(m+n) for each encode() and decode() function calls.

Space: O(m+n) for each encode() and decode() function calls.

(m = total length of all strings, n = number of strings)

Product of Array Except Self - Medium

Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].

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

Follow-up: Could you solve it in O(n)O(n) time without using the division operation?

Example 1:

Input: nums = [1,2,4,6]
Output: [48,24,12,8]

Example 2:

Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]

One left to right prefix product pass, then one right to left suffix project pass

Approach: Prefix & Suffix (optimal)

Time: O(n)

Space: O(n) space for the output array, O(1) extra space.

Valid Sudoku - Medium

Given a 9×9 Sudoku board (partially filled, empty cells are “.”), determine if the current state is valid. A board is valid if each row, each column, and each 3×3 sub-box contains the digits 1–9 at most once. You only validate the current state, not solvability.

One pass tracking seen values in row, column, and box sets (with box key - row//3, col//3)

Approach: Hash Set (One pass)

Time: O(n²)

Space: O(n²)

Longest Consecutive Sequence - Medium

Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

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

Example 1:

Input: nums = [2,20,4,10,3,4,5]
Output: 4

Example 2:

Input: nums = [0,3,2,5,4,6,1,1]
Output: 7

Put all numbers in a set; start counting a streak only from numbers whose predecessor is missing

Approach: Hash Set

Time: O(n)

Space: O(n)