Arrays

Question 1

Contains Duplicate (easy)

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

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

Answer 1

1. Use a hashset to store elements as you iterate through the array.
2. If an element is already in the set, return True (duplicate found).
3. If the loop completes, return False (no duplicates).

Time Complexity: O(n)
Space Complexity: O(n)

Question 2

Valid Anagram (easy)

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

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

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

Answer 2

1. If the length of s and t are not equal then return False.
2. Use a dictionary to count character frequencies for each string.
3. Compare the two dictionaries.

Time Complexity: O(n)
Space Complexity: O(1) because it’s limited to alphabet size

Question 3

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.

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

Answer 3

1. Create a dictionary to store the value and its index while iterating through the array.
2. For each element, calculate the complement: complement = target−current_value
3. Check if the complement is already in the dictionary. If yes, return the current index and the stored index of the complement. Otherwise, add the current value and index to the dictionary.

Time Complexity: O(n)
Space Complexity: O(n)

Question 4

Group Anagrams (med)

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.

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

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

Answer 4

1. Use a dictionary (defaultdict) to group strings.
2. Instead of sorting, represent each string by a character frequency count ([0] * 26 for 26 lowercase letters).
3. Iterate through each string and count the occurrences of each character.
4. Use the tuple of the frequency count as the key in the dictionary.
5. Append the string to the corresponding group.
6. Return the grouped values.

Time complexity: O(n*k) where n is number of strings and k is the number of characters in the string
Space complexity: O(n)

Question 4

Top K Frequent Elements (med)

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.

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

Answer 4

1. First, we count the frequency of each element in the nums array using a dictionary (count).
2. Bucket Creation (freq list): We create a list of lists (freq), where each index corresponds to a frequency count. If a number appears with frequency i, it is placed in the bucket at index i.
3. Building the Bucket: For each number in count, we append it to the corresponding bucket in freq based on its frequency.
4. Collecting Top K Frequent Elements: We iterate through freq starting from the highest frequency (the end of the list) and collect numbers until we have k elements. This ensures that the most frequent elements are selected first.

Time Complexity: O(n)
Space Complexity: O(n)

Question 5

Encode and Decode Strings (med)

Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.

Please implement encode and decode.

Answer 5

Encoding:
1. For each string, store its length followed by # and the string itself.
2. Concatenate all these encoded pieces into one string.

Time Complexity: O(n)
Space Complexity: O(1)

Decoding:
1. Traverse the encoded string.
2. Find the # separator to extract the length of each string.
3. Use the length to retrieve the actual string from the encoded string.

Time Complexity: O(n)
Space Complexity: O(1)

Question 6

Products of Array Except Self (med)

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.

Answer 6

Prefix Product:
Traverse the array from left to right, maintaining a running product (prefix) of all elements to the left of the current index. Store the result in res.

Postfix Product:
Traverse the array from right to left, maintaining a running product (postfix) of all elements to the right of the current index. Multiply the corresponding res[i] by postfix.

Time Complexity: O(n)
Space Complexity: O(1) since output array is excluded

Question 7

Valid Sudoku (med)

You are given a a 9 x 9 Sudoku board. A Sudoku board is valid if the following rules are followed:

Each row must contain the digits 1-9 without duplicates.
Each column must contain the digits 1-9 without duplicates.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.
Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Answer 7

1. Tracking Constraints: Use three sets to track the numbers encountered:
   rows: A dictionary of sets to track numbers in each row.
   cols: A dictionary of sets to track numbers in each column.
   squares: A dictionary of sets to track numbers in each 3x3 subgrid (indexed by (row//3, col//3)).
   Iterate Through the Board:
2. For each cell, if it’s filled, check if the number already exists in the corresponding row, column, or subgrid. If it does, return False (invalid board). Otherwise, add the number to the appropriate sets for the row, column, and subgrid.
3. If no conflicts are found after checking all cells, return True.

Time Complexity: O(n^2)
Space Complexity: O(n^2) since the number of sets in the dictionary is proportional to the grid size

Question 8

Longest Consecutive Sequence (med)

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.

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

Answer 8

1. Create a set from the input list to remove duplicates and allow O(1) lookups.
2. Iterate through each number in the set:
3. If the number minus 1 exists in the set, continue (this means the sequence has already been counted).
4. Otherwise, start a new sequence from the current number and check for consecutive numbers.
5. Track the maximum length of any consecutive sequence encountered.
6. Return the maximum length.

Time Complexity: O(n)
Space Complexity: O(n)