Problem Statement
Given an array of integers, identify the highest value that appears only once in the array. If no such number exists, return -1.
Examples:
-
Example 1:
- Input: [5, 7, 3, 7, 5, 8]
- Expected Output: 8
- Justification: The number 8 is the highest value that appears only once in the array.
-
Example 2:
- Input: [1, 2, 3, 2, 1, 4, 4]
- Expected Output: 3
- Justification: The number 3 is the highest value that appears only once in the array.
-
Example 3:
- Input: [9, 9, 8, 8, 7, 7]
- Expected Output: -1
- Justification: There is no number in the array that appears only once.
Constraints:
1 <= nums.length <= 20000 <= nums[i] <= 1000
Why this is a Hash Maps problem
| What the question says | The signal it matches |
|---|---|
| "identify the highest value that appears only once in the array" | the question says only, which is a statement about counts |
| a number qualifies on its count, then competes on its value | you count first, then reason about the counts |
| checking each number against the whole array to see if it repeats | your first idea is a nested loop that recounts the same thing |
Tallying every value and then scanning the tally is the count, then reason about the counts variant.
The closest alternative. Sorting also works. Once equal values are next to each other, a single pass finds the runs of length one and takes the largest. That costs O(N log N), and the only extra memory is the working space the sort itself needs.
The map answers in O(N) and pays memory for it. Either choice is defensible. Name the trade you are making.
Solution
To solve this problem, we utilize a hashmap to track the frequency of each number in the given array. The key idea is to iterate through the array, recording the count of each number in the hashmap. Once all elements are accounted for, we scan through the hashmap, focusing on elements with a frequency of one. Among these, we identify the maximum value. This approach ensures that we effectively identify the largest number that appears exactly once in the array, leveraging the hashmap for efficient frequency tracking and retrieval.
-
Initialization: Start by creating a hashmap that will be used to store the frequency of each number in the array. This hashmap will be instrumental in identifying numbers that appear only once.
-
Frequency Count: Traverse the entire array from the beginning to the end. For each number encountered, increment its count in the hashmap. This step ensures that by the end of the traversal, we have a complete record of how many times each number appears in the array.
-
Identify Largest Unique Number: After populating the hashmap, traverse it to identify numbers with a frequency of 1. While doing so, keep track of the largest such number. If no number with a frequency of 1 is found, the result will be -1.
-
Return Result: The final step is to return the largest number that has a frequency of 1. If no such number exists, return -1.
This approach, which leverages the properties of a hashmap, ensures that we can quickly determine the frequency of each number without the need for nested loops or repeated scans of the array.
Algorithm Walkthrough
5 is new, so it goes into the map with a count of 1. Each item is read once and stored once. Nothing is searched for.
1 of 12
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity: The algorithm traverses the array once to populate the hashmap and then traverses the hashmap to find the largest unique number. Both operations are O(n), where n is the length of the array. Therefore, the overall time complexity is O(n).
Space Complexity: The space complexity is determined by the hashmap, which holds one entry per distinct number in the array. The constraints keep every value between 0 and 1000, so the map can never hold more than 1001 entries however long the input is. That makes the extra space O(1) under these constraints. Without that bound on the values it would be O(d), where d is the number of distinct numbers.
.....
.....
.....