Watch 10 video solutions for Count Number of Distinct Integers After Reverse Operations, a medium level problem involving Array, Hash Table, Math. This walkthrough by Bro Coders has 809 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array nums consisting of positive integers.
You have to take each integer in the array, reverse its digits, and add it to the end of the array. You should apply this operation to the original integers in nums.
Return the number of distinct integers in the final array.
Example 1:
Input: nums = [1,13,10,12,31] Output: 6 Explanation: After including the reverse of each number, the resulting array is [1,13,10,12,31,1,31,1,21,13]. The reversed integers that were added to the end of the array are underlined. Note that for the integer 10, after reversing it, it becomes 01 which is just 1. The number of distinct integers in this array is 6 (The numbers 1, 10, 12, 13, 21, and 31).
Example 2:
Input: nums = [2,2,2] Output: 1 Explanation: After including the reverse of each number, the resulting array is [2,2,2,2,2,2]. The number of distinct integers in this array is 1 (The number 2).
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106Problem Overview: You are given an integer array nums. For every number, reverse its digits (e.g., 123 → 321) and add that reversed value back into the collection. After processing all numbers, return the count of unique integers that appear. The core challenge is tracking distinct values efficiently.
Approach 1: Using Set for Distinct Numbers (O(n * d) time, O(n) space)
This approach uses a set (or hash set) to automatically handle duplicates. Iterate through the array once. For each number, insert the original value into the set, compute its reversed form by repeatedly extracting digits (num % 10), and insert the reversed value as well. Hash sets guarantee average O(1) insertion and lookup, so the overall complexity depends mainly on processing digits during reversal. If d is the number of digits per integer, the total runtime becomes O(n * d) with O(n) space for storing unique numbers. This method works well because you never worry about duplicates—hashing handles them automatically.
The technique relies on efficient membership tracking using a hash table. Since the input is simply iterated once, it also aligns naturally with standard array traversal patterns.
Approach 2: Direct List Deduplication (O(n^2) time, O(n) space)
Another straightforward strategy is to store values in a list and manually check whether a value already exists before inserting it. Iterate through the original array, append the number if it does not already exist in the list, compute the reversed value, and again append it only if it is not present. The reversal logic still takes O(d), but the expensive step is the membership check. List searches require scanning existing elements, which leads to O(n) per check in the worst case.
Because each insertion may require a full scan of the list, the overall runtime grows to roughly O(n^2) for large inputs. Space usage remains O(n). This approach is easy to implement in scripting languages but becomes inefficient compared to hashing when the array size increases.
The problem itself combines basic math digit manipulation with simple counting of unique values.
Recommended for interviews: The hash set approach is what interviewers expect. It demonstrates awareness of constant-time lookups and clean handling of duplicates. A brute-force list check shows understanding of the problem mechanics, but the set-based solution shows you know how to optimize with the right data structure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Set for Distinct Numbers | O(n * d) | O(n) | General case. Best performance with large arrays because hash lookups are O(1). |
| Direct List Deduplication | O(n^2) | O(n) | Simple scripts or small datasets where implementing a set is unnecessary. |