Table: MyNumbers
+-------------+------+ | Column Name | Type | +-------------+------+ | num | int | +-------------+------+ This table may contain duplicates (In other words, there is no primary key for this table in SQL). Each row of this table contains an integer.
A single number is a number that appeared only once in the MyNumbers table.
Find the largest single number. If there is no single number, report null.
The result format is in the following example.
Example 1:
Input: MyNumbers table: +-----+ | num | +-----+ | 8 | | 8 | | 3 | | 3 | | 1 | | 4 | | 5 | | 6 | +-----+ Output: +-----+ | num | +-----+ | 6 | +-----+ Explanation: The single numbers are 1, 4, 5, and 6. Since 6 is the largest single number, we return it.
Example 2:
Input: MyNumbers table: +-----+ | num | +-----+ | 8 | | 8 | | 7 | | 7 | | 3 | | 3 | | 3 | +-----+ Output: +------+ | num | +------+ | null | +------+ Explanation: There are no single numbers in the input table so we return null.
This approach involves using a hash map or dictionary to count the number of occurrences of each integer in the array. After counting, we identify numbers that appeared only once and find the maximum among them. This way, we can efficiently determine the largest single number.
In this C code, we define a structure to store the integers and their counts. We iterate through the array, counting occurrences. After populating the list, we sort it and look for the largest number with a count of 1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) in worst case for counting and sorting (since sorting involves iterating the elements list).
Space Complexity: O(n) for storing numbers and their counts.
This approach involves sorting the numbers first. After sorting, we can iterate through the list to count numbers that appear consecutively more than once and skip them. The largest number with only one occurrence is then the answer.
In this C solution, we first sort the array in descending order. This allows us to iterate and find the largest number that is not duplicated (previous or next number does not match).
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we sort in place.
| Approach | Complexity |
|---|---|
| Using HashMap/Dictionary for Count Tracking | Time Complexity: O(n^2) in worst case for counting and sorting (since sorting involves iterating the elements list). |
| Using Sorting for Efficient Search | Time Complexity: O(n log n) due to sorting. |
Single Number - Leetcode 136 - Python • NeetCode • 117,991 views views
Watch 9 more video solutions →Practice Biggest Single Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor