Solving LeetCode Single Number Problem for Data Science Interviews

How does a data scientist solve the LeetCode Single Number problem in Python to prepare for their data science interviews?

Using LeetCode To Solve Python Questions

LeetCode has a massive database of real interview questions which companies like Amazon, Google, Microsoft, Facebook, and other giants have asked. LeetCode’s designers built it specifically for software developers, and developers generally consider it an amazing resource with over 1599 algorithm-based questions among a variety of languages. Since data scientists most commonly use Python and SQL, data scientists use LeetCode to improve their skills and prepare for data science interviews.

We are going to look at a specific LeetCode Single Number problem today which we’ll solve in three different ways via Python. It is one of many Python problems useful for preparing for data science interviews.
On StrataScratch.com, we also have several other articles discussing "How To Use LeetCode For Data Science SQL Interviews" and "LeetCode Python Solutions for Data Science".

Solving the LeetCode Single Number Problem

136. Single Number

Interviewers have asked the single number question a variety of ways in data science interviews. The key challenge is finding the single array element which only appears once in an array of integers. While one of the demands is implementing a solution with linear runtime complexity and constant extra space, we’ll see there are several ways to meet this criteria.

Link: https://LeetCode.com/problems/single-number

In this LeetCode Single Number problem, we’re being asked to find the only integer which appears once in an array of data where every other integer appears twice. We know immediately any solutions for this LeetCode Single Number Problem will require thinking in advance about the complexity and space of the computation.

This LeetCode single number problem may seem daunting given the constraints, but, as we will see, there are several solutions with varying levels of complexity and space requirements. Today, we’re going to look at three solutions which approach the problem differently: through using a counter, through mathematics, and through bitwise manipulation.

Framework to Solve this LeetCode Single Number Problem

The easiest way to solve data science interview questions whether in Python, SQL, or some other language is to use a generally applicable framework. Here’s a framework we use for all data science problems on StrataScratch which we’ll adapt to this problem. You’ll see it provides logical steps for how to arrive at the correct answer:

1. Understand Your Data
   1. This LeetCode single number problem gives sample data to look at. See if you notice any patterns in the arrays or anything which might require you to adjust your algorithms. This will help you identify the bounds to which you should limit your solution as well as uncover edge cases.
   2. Typically LeetCode provides more than one snippet of sample data. If the first example isn’t sufficient, spend some time with the other data they provide. In an interview, you can attempt to explain your current understanding of the data to the interviewer and ask them for feedback.
2. Formulate your approach:
   1. Now write down all the steps you’ll need for coding your solution. Consider how Python computes and what functions you’ll need to leverage. Also keep in mind how complex they’ll make your solution.
   2. Don’t forget the interviewer will be observing you. Don’t hesitate to ask them for help. They’ll often specify any additional limitations which apply to your Python code.
3. Code Execution
   1. Try to keep your Python code simple in this LeetCode single number problem since complexity and space are concerns.
   2. Follow the steps you laid out in the beginning. Even if it’s not the most efficient way to solve the problem, you can explain potential optimizations afterwards as long as you hit the problem’s complexity and space requirements.
   3. Don’t convolute your card. This might make it difficult for both you and the interview to understand your solution and could introduce unknown results or complexity.
   4. Speak through your solution with the interviewer as you write down your Python. They want to understand how you think as you advance towards an answer.

Understand your data

Let’s start by looking at some of the data. Fortunately, LeetCode will typically provide you with several examples to look at.

In this case we receive three example arrays of integers. Each array contains an element which only appears once and other elements which appear twice.

From the three examples, we can already notice a few patterns:

1. Your solution should work for arrays with only one or two discrete integers.
2. Your solution should work for arrays with several pairs of discrete integers where the duplicate elements aren’t consecutive.

We are also given some constraints to work with:

These constraints aren’t particularly important for the solutions we’ll cover in this article, but you should always be aware of the limits of the problem.

What’s important to realize is we need a solution to account for a variety of array sizes and content which still only maintains linear complexity and constant extra space.

Solution 1:

For our first solution, we use a common Python function called a counter to count all elements in the array and then filter for the element with a count of one.

Formulate Approach

The next step, according to our previous framework, is to outline some steps we’ll need to take. Writing down the steps you’ll take in advance will make coding significantly easier.

For our first solution, here are the general steps we’ll follow:

1. We use a COUNTER function in Python to go through all the elements in the array and return a dictionary of how many times any given element appears.
2. We filter the result of the counter dictionary to find the element where the count is equal to 1. Since we expect only one element to appear once, we can return the first match.

Code execution

To write the Python code for this question, let’s follow the steps we just wrote down and translate them to code. The most important part of this solution is correctly applying the count function on our array and filtering the result.

Looking at the first step, we can start by writing the code for counting the elements in the array.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        c = Counter(nums)
        return c

Given one of our example inputs, our solution will now return a dictionary giving the total count of each integer in our input array. We immediately see one of our integers only has a count of one. Next, all we have to do is filter for this element. To do this, we’ll use a FOR loop to find the first dictionary key with a value equal to one.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        c = Counter(nums)
        for n in c:
            if c[n] == 1:
            		return n

Now we arrive at the correct answer with our solution presenting us with the only integer which doesn’t appear twice in the input array.

When it comes to complexity and space, this answer meets the original criteria. Creating a counter and going through it once only requires O(n) runtime complexity. Furthermore, the comparison lookup in our loop only requires O(1) (constant) space.

Solution 2:

Our second solution relies on comparing sums in Python. Since sets reduce all elements to a single occurrence, we can use the set function and algebra to calculate the integer which appears only once.

Formulate Approach

Following our framework again, we need to start our second solution by writing down some specific steps:

1. We first apply the SET function to reduce our input array to an array only containing one occurrence of each original integer element.
2. We sum our set and double it using arithmetic operations to prepare our comparison.
3. We then subtract the sum of the elements in our original array to isolate the single element which appears once.

Code execution

Let’s again follow the steps we just wrote down and translate them into code. The critical component of this solution is correctly applying the algebra to your set and input array, otherwise you’ll yield the incorrect output.

Looking at the first step, let’s apply the set function to our array to understand how it changes our input array.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return set(nums)

We see the original array has been reduced to a set consisting of all the elements without repetition.

Next we need to sum our set and double it. The specific mathematics behind this answer depends on the question being asked. Because we know all elements but 1 appear only twice, we can double the sum of our set. If they appeared perhaps three or four times, our math would change and doubling our set might be insufficient.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return 2*sum(set(nums))

Now we yield an integer as an output, but it is not yet the element which only appears once. In order to calculate our answer, we must now subtract the sum of our original array. Given we DO NOT use a set function again to reduce the array, our sum will differ from our existing calculation by the correct output.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return 2*sum(set(nums))-sum(nums)

When it comes to complexity and space, this answer doesn’t optimize any further than our first code snippet. Sum and set both go through the entire array, and it still requires space to store the set. As a result, we get O(n) for both runtime and space complexity.

Solution 3:

Our third solution relies on bitwise manipulation using the XOR operator. For context, if we take the XOR of 0 and some bit, it will return the bit. However, if we take the XOR of the same two elements, it will return 0. As such, every element which appears twice is going to yield 0 via a XOR operation, and the element appearing once is going to yield itself after a XOR with the 0 result from all the other duplicate elements.

Formulate Approach

Looking back at our framework - we need to again begin our third solution by writing down our coding steps:

1. We know we’ll need to perform a bitwise comparison of all elements, so we’ll need to start by looping through our array and establishing a variable for our first XOR operation.
2. Using the XOR operator, perform the XOR bitwise operation on each element of your array starting with the first element operated against 0.
3. Simplify the solution by instead storing the result of each XOR operation in the first index of the input array. Then return the element at index 0 after the first loop through the array.

Code execution

Time to again translate our steps into functional code. The key to this solution is performing the XOR operation against the result of previous XOR operations instead of performing an XOR operation on each element against itself.

Looking at the first step, let’s establish a 0 variable to XOR against and loop through our array starting with the first element.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
		a = 0
        for i in nums:

Now we need to XOR every element of our array against our a variable. Since a starts as 0, we know the first XOR operation will yield the first element. We can reassign the result of this operation to the a variable to XOR the rest of the elements. Finally, we return the end result of all these XOR operations.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = 0
        for i in nums:
            a ^= i
        return a

This already yields us a correct answer, but the solution is not yet optimized. While it has a complexity of O(1), it does not yet have space optimization. You can save space by storing the result of the XOR operations in the first index of the array instead of creating a variable to store it in.

We’ll need to change our loop in this case since you can now start with the 2nd index instead of the 1st. Keep in mind the first element will already be part of the first XOR operation.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
	        nums[0] ^= nums[i]
        return nums[0]

We see our solution is again correct, but this time we didn’t have to make an extra storage variable. We end up using less space, and, as such, present the interviewer with a more efficient solution.

Comparison of Approaches to Solve this LeetCode Single Number Question

We have gone through 3 different ways you can solve this LeetCode single number question. While all of them are correct and result in the expected output, the solutions differ in their computations and complexity.

The first difference is to take note of how each approach solves the problem. Our first approach uses the counter function, our second approach arrives upon the solution mathematically, and our third approach leverages bitwise manipulation. As you work your way through interview questions similar to this one, consider how there may be different computational methods you can apply. This may open up solutions you weren’t considering at first.

The second issue has to do with complexity and storage. While we’re already given constraints for linear complexity and constant extra space, we ideally present our interviewer with the most optimal code we can write.

Looking back, our counter and mathematical solution both maintain O(n) complexity and O(n) space since they must calculate through the entire array and store it. However, our bitwise manipulation solution only requires complexity O(1) given it only needs to calculate between two elements at a time and requires minimal space since it stores the result of each XOR operation in the first element of the array.

For these types of problems, you should prepare yourself to explain why different solutions yield different complexity and space requirements. In addition, it’s helpful to understand the computational differences between separate solutions to the same problem.

Conclusion

In this article, we covered several different ways for solving a LeetCode Single Number Python data science problem. Many of the questions interviewers give you during data science interviews will be similar to this problem. Keep in mind this article’s three methods are not the only ways to solve this problem, and there exist many other solutions of greater or lesser complexity and space requirements.

On StrataScratch, you will find articles discussing many other python interview questions you will encounter in data science interviews. Beyond interview questions and answers, you will also find general articles on how to succeed in your data science interview as well as an interactive area to practice answering data science interview questions by constructing your own solutions or reviewing others’ solutions, and even more general articles like "LeetCode vs HackerRank vs StrataScratch for Data Science" where we compared these three interview preparation platforms which are used by people working in Data Science.