Count Number of Distinct Integers After Reverse Operations - Solution & Explanation
Problem Statement
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] <= 106
Approach Overview
Problem 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 1: Using Set for Distinct Numbers
This approach utilizes a Set to keep track of distinct integers. We process each number by reversing its digits and add both the original and reversed numbers to the Set, which automatically ensures there are no duplicates. The result will be the size of the Set, which represents the number of distinct integers.
The C solution employs a hash set array to track the presence of numbers, taking advantage of the constraints that numbers are between 1 and 1,000,000. We reverse each number and ensure both the original and reversed versions are stored in the hash set. This ensures uniqueness and allows for quick lookups.
Complexity
Time Complexity: O(n * d), where n is the size of the array and d is the number of digits in the largest number. Space Complexity: O(1), considering the constant space size of the hash array due to number constraints.
Approach 2: Using Direct List Deduplication
This approach directly appends both original and reversed numbers to a new array and then extracts unique numbers by leveraging available inbuilt functions specific to each programming language. This results in a list with only distinct numbers.
This JavaScript solution uses an array to store all numbers and their reversals, then transforms the array into a Set to eliminate duplicates, taking advantage of JavaScript's built-in data structures for achieving deduplication simply and efficiently.
Code
JavaScript
Python
Complexity
Time Complexity: O(n * d), where n is the size of the array and d is the average number of digits. Space Complexity: O(n) due to the list and the Set used for deduplication.
Approach 3: Hash Table
First, we use a hash table to record all integers in the array. Then, we traverse each integer in the array, reverse it, and add the reversed integer to the hash table. Finally, we return the size of the hash table.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Set for Distinct Numbers | Time Complexity: O(n * d), where n is the size of the array and d is the number of digits in the largest number. Space Complexity: O(1), considering the constant space size of the hash array due to number constraints. |
| Using Direct List Deduplication | Time Complexity: O(n * d), where n is the size of the array and d is the average number of digits. Space Complexity: O(n) due to the list and the Set used for deduplication. |
| Hash Table | — |
Detailed Complexity Analysis
| 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. |
Video Solution
2442 Count Number of Distinct Integers After Reverse Operations | Leetcode Weekly 315| LeetCode 2442 • Bro Coders • 824 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Number of Distinct Integers After Reverse Operations easy or hard?
Count Number of Distinct Integers After Reverse Operations Python/Java solution
How to solve Count Number of Distinct Integers After Reverse Operations in O(n)?
What is the best approach for Count Number of Distinct Integers After Reverse Operations?
Is Count Number of Distinct Integers After Reverse Operations asked at Google/Amazon/Meta?
What data structure is used in Count Number of Distinct Integers After Reverse Operations?
What is the time complexity of Count Number of Distinct Integers After Reverse Operations?
Ready to solve this problem?
Practice Count Number of Distinct Integers After Reverse Operations with our built-in code editor and test cases.
Practice on FleetCode