Scale Engineer

Single Number

Easy
#0136Time: O(n^2)Space: O(1)10 companies
Patterns
Bit Manipulation
Data structures
Array
Companies
AirbnbCiscoGoogleNvidia

Prompt

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.

Approaches

4 approaches with complexity analysis and trade-offs.

This approach uses nested loops to find the single number. For each element in the array, we iterate through the entire array again to count its occurrences. If an element's count is one, it is the unique element.

Algorithm

    1. Iterate through the array with an outer loop from i = 0 to n-1.
    1. For each element nums[i], initialize a count variable to 0.
    1. Start an inner loop from j = 0 to n-1.
    1. Inside the inner loop, if nums[i] is equal to nums[j], increment count.
    1. After the inner loop finishes, check if count is equal to 1.
    1. If count is 1, nums[i] is the single number. Return nums[i].

Walkthrough

The brute force method is the most straightforward way to solve the problem, but also the least efficient. The core idea is to check every element and see how many times it appears in the array.

We use two nested loops. The outer loop picks an element, and the inner loop iterates through the entire array to count the occurrences of the picked element. If the count for an element is exactly one, we have found our single number and can return it immediately.

public int singleNumber(int[] nums) {    for (int i = 0; i < nums.length; i++) {        int count = 0;        for (int j = 0; j < nums.length; j++) {            if (nums[i] == nums[j]) {                count++;            }        }        if (count == 1) {            return nums[i];        }    }    return -1; // Should not be reached given the problem constraints}

Complexity

Time

O(n^2)

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space.

Cons

  • Highly inefficient with a quadratic time complexity.

  • Will likely result in a 'Time Limit Exceeded' error for large inputs.

Solutions

public class Solution {    public int SingleNumber(int[] nums) {        return nums.Aggregate(0, (a, b) => a ^ b);    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem