Arrays & Hashing

Given an integer array `nums`, return `true` if any value appears **more than once** in the array, otherwise return `false`. **Example 1:** ```java Input: nums = [1, 2, 3, 3] Output: true ``` <br> **Example 2:** ```java Input: nums = [1, 2, 3, 4] Output: false ``` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to check every element against every other element in the array. This would be an <code>O(n^2)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Is there a way to check if an element is a duplicate without comparing it to every other element? Maybe there's a data structure that is useful here. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use a hash data structure like a hash set or hash map to store elements we've already seen. This will allow us to check if an element is a duplicate in constant time. </p> </details>

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. **Example 1:** ```java Input: s = "racecar", t = "carrace" Output: true ``` **Example 2:** ```java Input: s = "jar", t = "jam" Output: false ``` **Constraints:** * `s` and `t` consist of lowercase English letters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n + m)</code> time and <code>O(1)</code> space, where <code>n</code> is the length of the string <code>s</code> and <code>m</code> is the length of the string <code>t</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to sort the given strings and check for their equality. This would be an <code>O(nlogn + mlogm)</code> solution. Though this solution is acceptable, can you think of a better way without sorting the given strings? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> By the definition of the anagram, we can rearrange the characters. Does the order of characters matter in both the strings? Then what matters? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can just consider maintaining the frequency of each character. We can do this by having two separate hash tables for the two strings. Then, we can check whether the frequency of each character in string <code>s</code> is equal to that in string <code>t</code> and vice versa. </p> </details>

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:** ```java Input: nums = [3,4,5,6], target = 7 Output: [0,1] ``` Explanation: `nums[0] + nums[1] == 7`, so we return `[0, 1]`. **Example 2:** ```java Input: nums = [4,5,6], target = 10 Output: [0,2] ``` **Example 3:** ```java Input: nums = [5,5], target = 10 Output: [0,1] ``` **Constraints:** * `2 <= nums.length <= 1000` * `-10,000,000 <= nums[i] <= 10,000,000` * `-10,000,000 <= target <= 10,000,000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where n is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to check every pair of numbers in the array. This would be an <code>O(n^2)</code> solution. Can you think of a better way? Maybe in terms of mathematical equation? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Given, We need to find indices <code>i</code> and <code>j</code> such that <code>i != j</code> and <code>nums[i] + nums[j] == target</code>. Can you rearrange the equation and try to fix any index to iterate on? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> we can iterate through nums with index <code>i</code>. Let <code>difference = target - nums[i]</code> and check if <code>difference</code> exists in the hash map as we iterate through the array, else store the current element in the hashmap with its index and continue. We use a hashmap for <code>O(1)</code> lookups. </p> </details>

Given an array of strings `strs`, group all *anagrams* together into sublists. Give any solution out of multiple solutions. 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:** ```java Input: strs = ["act","pots","tops","cat","stop","hat"] Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]] ``` **Example 2:** ```java Input: strs = ["x"] Output: [["x"]] ``` **Example 3:** ```java Input: strs = [""] Output: [[""]] ``` **Constraints:** * `1 <= strs.length <= 1000`. * `0 <= strs[i].length <= 100` * `strs[i]` is made up of lowercase English letters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(m * n)</code> time and <code>O(m)</code> space, where <code>m</code> is the number of strings and <code>n</code> is the length of the longest string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A naive solution would be to sort each string and group them using a hash map. This would be an <code>O(m * nlogn)</code> solution. Though this solution is acceptable, can you think of a better way without sorting the strings? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> By the definition of an anagram, we only care about the frequency of each character in a string. How is this helpful in solving the problem? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can simply use an array of size <code>O(26)</code>, since the character set is <code>a</code> through <code>z</code> (<code>26</code> continuous characters), to count the frequency of each character in a string. Then, we can use this array as the key in the hash map to group the strings. </p> </details>

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:** ```java Input: nums = [1,2,2,3,3,3], k = 2 Output: [2,3] ``` **Example 2:** ```java Input: nums = [7,7], k = 1 Output: [7] ``` **Constraints:** * `1 <= nums.length <= 10^4`. * `-1000 <= nums[i] <= 1000` * `1 <= k <= number of distinct elements in nums`. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A naive solution would be to count the frequency of each number and then sort the array based on each element’s frequency. After that, we would select the top <code>k</code> frequent elements. This would be an <code>O(nlogn)</code> solution. Though this solution is acceptable, can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Can you think of an algorithm which involves grouping numbers based on their frequency? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Use the bucket sort algorithm to create <code>n</code> buckets, grouping numbers based on their frequencies from <code>1</code> to <code>n</code>. Then, pick the top <code>k</code> numbers from the buckets, starting from <code>n</code> down to <code>1</code>. </p> </details>

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` **Example 1:** ```java Input: ["neet","code","love","you"] Output:["neet","code","love","you"] ``` **Example 2:** ```java Input: ["we","say",":","yes"] Output: ["we","say",":","yes"] ``` **Constraints:** * `0 <= strs.length < 100` * `0 <= strs[i].length < 200` * `strs[i]` contains only UTF-8 characters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(m)</code> time for each <code>encode()</code> and <code>decode()</code> call and <code>O(m+n)</code> space, where <code>m</code> is the sum of lengths of all the strings and <code>n</code> is the number of strings. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A naive solution would be to use a non-ascii character as a delimiter. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Try to encode and decode the strings using a smart approach based on the lengths of each string. How can you differentiate between the lengths and any numbers that might be present in the strings? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use an encoding approach where we start with a number representing the length of the string, followed by a separator character (let's use <code>#</code> for simplicity), and then the string itself. To decode, we read the number until we reach a <code>#</code>, then use that number to read the specified number of characters as the string. </p> </details>

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)$ time without using the division operation? **Example 1:** ```java Input: nums = [1,2,4,6] Output: [48,24,12,8] ``` **Example 2:** ```java Input: nums = [-1,0,1,2,3] Output: [0,-6,0,0,0] ``` **Constraints:** * `2 <= nums.length <= 1000` * `-20 <= nums[i] <= 20` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute-force solution would be to iterate through the array with index <code>i</code> and compute the product of the array except for that index element. This would be an <code>O(n^2)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Is there a way to avoid the repeated work? Maybe we can store the results of the repeated work in an array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use the prefix and suffix technique. First, we iterate from left to right and store the prefix products for each index in a prefix array, excluding the current index's number. Then, we iterate from right to left and store the suffix products for each index in a suffix array, also excluding the current index's number. Can you figure out the solution from here? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use the stored prefix and suffix products to compute the result array by iterating through the array and simply multiplying the prefix and suffix products at each index. </p> </details>

You are given a `9 x 9` Sudoku board `board`. A Sudoku board is valid if the following rules are followed: 1. Each row must contain the digits `1-9` without duplicates. 2. Each column must contain the digits `1-9` without duplicates. 3. 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. **Example 1:**  ```java Input: board = [["1","2",".",".","3",".",".",".","."], ["4",".",".","5",".",".",".",".","."], [".","9","8",".",".",".",".",".","3"], ["5",".",".",".","6",".",".",".","4"], [".",".",".","8",".","3",".",".","5"], ["7",".",".",".","2",".",".",".","6"], [".",".",".",".",".",".","2",".","."], [".",".",".","4","1","9",".",".","8"], [".",".",".",".","8",".",".","7","9"]] Output: true ``` **Example 2:** ```java Input: board = [["1","2",".",".","3",".",".",".","."], ["4",".",".","5",".",".",".",".","."], [".","9","1",".",".",".",".",".","3"], ["5",".",".",".","6",".",".",".","4"], [".",".",".","8",".","3",".",".","5"], ["7",".",".",".","2",".",".",".","6"], [".",".",".",".",".",".","2",".","."], [".",".",".","4","1","9",".",".","8"], [".",".",".",".","8",".",".","7","9"]] Output: false ``` Explanation: There are two 1's in the top-left 3x3 sub-box. **Constraints:** * `board.length == 9` * `board[i].length == 9` * `board[i][j]` is a digit `1-9` or `'.'`. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n^2)</code> time and <code>O(n^2)</code> space, where <code>n</code> is the number of rows in the square grid. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Which data structure would you prefer to use for checking duplicates? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> You can use a hash set for every row and column to check duplicates. But how can you efficiently check for the squares? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can find the index of each square by the equation <code>(row / 3) * 3 + (col / 3)</code>. Then we use hash set for <code>O(1)</code> lookups while inserting the number into its row, column and square it belongs to. We use separate hash maps for rows, columns, and squares. </p> </details>

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:** ```java Input: nums = [2,20,4,10,3,4,5] Output: 4 ``` Explanation: The longest consecutive sequence is `[2, 3, 4, 5]`. **Example 2:** ```java Input: nums = [0,3,2,5,4,6,1,1] Output: 7 ``` **Constraints:** * `0 <= nums.length <= 1000` * `-10^9 <= nums[i] <= 10^9` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to consider every element from the array as the start of the sequence and count the length of the sequence formed with that starting element. This would be an <code>O(n^2)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Is there any way to identify the start of a sequence? For example, in <code>[1, 2, 3, 10, 11, 12]</code>, only <code>1</code> and <code>10</code> are the beginning of a sequence. Instead of trying to form a sequence for every number, we should only consider numbers like <code>1</code> and <code>10</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can consider a number <code>num</code> as the start of a sequence if and only if <code>num - 1</code> does not exist in the given array. We iterate through the array and only start building the sequence if it is the start of a sequence. This avoids repeated work. We can use a hash set for <code>O(1)</code> lookups by converting the array to a hash set. </p> </details>