You are given an integer array digits, where each element is a digit. The array may contain duplicates.
You need to find all the unique integers that follow the given requirements:
digits in any arbitrary order.For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.
Return a sorted array of the unique integers.
Example 1:
Input: digits = [2,1,3,0] Output: [102,120,130,132,210,230,302,310,312,320] Explanation: All the possible integers that follow the requirements are in the output array. Notice that there are no odd integers or integers with leading zeros.
Example 2:
Input: digits = [2,2,8,8,2] Output: [222,228,282,288,822,828,882] Explanation: The same digit can be used as many times as it appears in digits. In this example, the digit 8 is used twice each time in 288, 828, and 882.
Example 3:
Input: digits = [3,7,5] Output: [] Explanation: No even integers can be formed using the given digits.
Constraints:
3 <= digits.length <= 1000 <= digits[i] <= 9This approach revolves around using a hash map (or dictionary in Python) to keep track of the elements we have encountered so far. The primary idea is to utilize the hash map's average O(1) time complexity for insertion and lookup to solve the problem efficiently.
This C implementation uses separate chaining to handle hash collisions. The hashTable is an array of linked lists (represented by Node structures). The program inserts each unique element from the input array into the hash table and prints unique elements.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for both insertion and lookup in the average case.
Space Complexity: O(n) for storing the elements.
This approach involves first sorting the array and then performing a linear pass to ensure uniqueness. By sorting, duplicate elements appear consecutively, making it easy to skip them during the final pass.
The C solution first sorts the array using qsort and then iterates through the sorted array. Only elements different from their predecessors are printed, achieving uniqueness.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) additional space if in-place sorting is feasible.
| Approach | Complexity |
|---|---|
| Approach 1: Using a Hash Map | Time Complexity: O(n) for both insertion and lookup in the average case. |
| Approach 2: Sorting and Linear Pass | Time Complexity: O(n log n) due to sorting. |
I solved too many Leetcode problems • NeetCodeIO • 101,495 views views
Watch 9 more video solutions →Practice Finding 3-Digit Even Numbers with our built-in code editor and test cases.
Practice on FleetCode