class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
result ^= num
return result
Hello everyone! Today I solved three tasks on LeetCode, Single Number, First Missing Positive, and Next Greater Element III. Coming through these solving processes, I reached a conclusion that we, all of us together with myself, tend to do the same mistakes more than once. For example, if we encounter an easy problem, we would rush through it and then use a known solution to solve it quickly and get out of the way. However, one has to take time to stop and reflect on his or her solution and ask himself or herself whether that is the best way to use to be efficient. If it's not, then one must take time to learn and implement a better solution.
The Single Number problem is a nice example of this. It is an easy problem where you are to find in the list that number that appears just once while all the rest appear twice. First, I have used for this a hash map, and indeed it works but of course it's not optimal. Further search revealed also another, yet faster, solution based on the XOR operation.
The next problem that I solved was First Missing Positive. It asks for finding the smallest positive integer missing from an unsorted array. I thought of sorting the array and then iterating through it, but sorting will take not optimal. Further problem analysis revealed that I could use the array itself as a hash map. Placing each number in its correct index (for example, putting 1 at index 0) and then scanning the array to find the first index where the number isn't correct gives this method a time complexity of O(n) and space complexity of O(1), which is much more efficient than my original idea.
Finally, Next Greater Element III was the toughest of the three. Problem: For a given number, find the smallest number bigger than that which can be made from rearranging digits. Then I swapped the pivot with the smallest digit on its right that's bigger and then I reversed the digits to the right of the pivot to get me a number that has got as small a value as possible. Even though the above solution took a pretty long time to think out, it is in steps breaking logic that makes this so easy to implement with the code.
Hope my experience helps you approach coding challenges with more thoughtfulness and confidence. Happy coding!
Top comments (0)