Permutations II
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2], [1,2,1], [2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8-10 <= nums[i] <= 10
Solution
Let's fill in the logic for backtracking1:
path_length: indicates the number of elements inpathused: an array storing the status of whether an element is used.is_leaf:path_length == len(nums), whenpath_lengthis the same asnums's length.get_edgesandis_valid: all elements that are unused (used[i]==Flase).
In the implementation, we use an array used to store the whether an element has been used or not.
Everytime we use a number, we add it into the path and we mark it used (used[idx] = True).
Since there are duplicate values, let's apply methods in Deduplication to deduplicate the results.
we want to sort the nums array so that duplicate elements are consecutive, and only proceed when the current element is the first of its occurrance.
Implementation
1def permuteUnique(self, nums: List[int]) -> List[List[int]]:
2 used = [False] * len(nums)
3 ans = []
4 nums.sort()
5
6 def dfs(path_length, path):
7 if path_length == len(nums):
8 ans.append(path[:])
9 return
10
11 for i in range(0, len(nums)):
12 if used[i]: continue
13 if(i > 0 and nums[i] == nums[i-1] and not used[i-1]): continue
14 path.append(nums[i])
15 used[i] = True
16 dfs(path_length + 1, path)
17 used[i] = False
18 path.pop()
19
20 dfs(0, [])
21 return ans
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Solution Implementation
Which data structure is used to implement recursion?
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.