First Missing Positive
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
'''Step 1 -> The main idea behind it is that the minimum number to be found will always be in the range [1....n]
where 'n' is the length of list. So keep numbers in this range and mark others
(here we are marking them with (n+1) value) in the list provided.'''
n = len(nums)
for i in range(n):
if nums[i] < 1 or nums[i] > n:
nums[i] = n + 1
'''Step 2 -> Ignoring the values greater than 'n', mark the indexes of the numbers in the range [1...n]
so as to ensure that this values are present. To mark the indexes,
I am negating the value present at that index.'''
for i in range(n):
val = abs(nums[i])
if val > n:
continue
val -= 1 #since the list is zero indexed,so every value will be at position val - 1
if nums[val] > 0:
# For similar numbers, it will keep on fluctuating between negative and positive
# which is not our motive here.
nums[val] = -1 * nums[val]
'''Step 3 -> Return the first occurence of the non-negative numbers from the list'''
for i in range(n):
if nums[i] >=0:
return (i + 1) # bcoz list is zero indexed
'''Step 4 -> We will encounter this if no positives were found. This means that all the
numbers are in the range [1....n]. So the missing positive number will be n+1'''
return (n + 1)Related Problems
Given a function fn, return a curried version of that function.
A curried function is a function that accepts fewer or an equal number of parameters as the original function and returns either another curried function or the same value the original function would have returned.
In practical terms, if you called the original function like sum(1,2,3), you would call the curried version like csum(1)(2)(3), csum(1)(2,3), csum(1,2)(3), or csum(1,2,3). All these methods of calling the curried function should return the same value as the original.
The Hamming Distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, return the Hamming distance between them.
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".