Leetcode - Day 1

Problem 1: Contains Duplicate ( Leetcode 217 )

Example: [ 1,2,2,4 ] Return True | [1,2,3] Return False

Solution:

i) Brute Force

n = len(nums)
for i in range(n):
for j in range(i+1, n):
if nums[i] == nums[j]:
return True
return False

ii) Using Sort

If we sort the array, the duplicates will come close to each other, all that remains is comparing adjacent elements, this reduces the complexity from O(n^2) to O(n logn).

nums.sort()
for i in range(len(nums)-1):
if nums[i] == nums[i+1]:
return True
return False

iii) Using Set => This one honestly did not strike me at all at first. It reminded me that data structures and fundamentals of Python matter. A lot.

Sets do not allow duplicates. So if the length of our list = n and length of set(list) => No duplicates present, return False, else return True.

if len(set(nums))==len(nums):
return False
else:
return True

Problem 2: Missing Number (Leetcode 268)

Example: [0,1,3] => 3 number, so range = [0,3] = [0,1,2,3] => 2 is missing | [0,1] => Range [0,2] = [0,1,2] => 2 is missing.

Solution

i) Brute Force

n = len(nums)
for i in range(n+1):
if i not in nums:
return i

ii) Sorting

Create the range according to length of nums [0,1,2,3] , now compare each element of range with sorted nums [0,1,3]

'nums.sort()
for i in range(len(nums)):
if nums[i] != i:
return i
return len(nums)`

iii) Math\Gauss Formula

Honestly, this felt satisfying when it clicked. Sum from 0 to n minus sum of array gives the missing number.
0+1+2+3 => 6
0+1+3 => 4
6-4 = 2 => Missing number

n = len(nums)
expected = n * (n + 1) // 2
actual = sum(nums)
return expected - actual

iv) XOR Method
Looked at this in LC solutions. Smart trick, but early on can feel confusing. Personally I will stick with the math one.

'res = 0
for i in range(len(nums)+1):
res ^= i
for num in nums:
res ^= num
return res`

Explanation: For XOR gate, x^x = 0 and x^0 = x. In this method we will keep a bucket (res in code). First we will take XOR with range.
Current bucket = 0

Bucket | Range

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 2 = 3 (Convert to binary then take XOR)
3 ^ 3 = 0

Current bucket = 0
Now we will take XOR with nums

0 ^ 3 = 3
3 ^ 0 = 3
3 ^ 1 = 2
Final answer = 2

Problem 3: Find All Numbers Disappeared in an Array (Leetcode 448)

This is kind of similar to Problem 1, I Used set logic here too.

n = len(nums)
num_set = set(nums)
result = []
for i in range(1, n+1):
if i not in num_set:
result.append(i)
return result

Problem 4: Two sum (Leetcode 1)

i) Brute Force:

for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]

ii) HashMap Approach:

Store each number with its index in a dictionary while you iterate. For every new number, check if the target minus this number already exists in the dictionary. If yes, done.

This was my first time really thinking in terms of a hash map instead of just using Python dictionaries randomly. Felt good.

'seen = {}
for i, num in enumerate(nums):
rem = target - num
if rem in seen:
return [seen[rem], i]
seen[num] = i'

My Takeaway:

Always start with brute force. Don’t start thinking of the optimal solution right away. You won’t be able to reach it unless you’ve already memorized it and that’s a different case. In interviews too, recruiters want to see your thought process, not just the final optimized solution. They want to see how, step by step, you eventually reach the optimal one, starting from brute force.