Problem Solving

Top Problems must be revised before interview

Array

Binary Search On Sorted Array

Binary Search is the most efficient way to search in Sorted array.
Time Complexity : O(logn)
Space Complexity : O(1) (iterative Solution), O(logn) recursive Solution

Iterative Solution Of Binary Search

first initialize two variables (low,high) with 0 and length of array
start a loop which ends when low becomes equal or greater than high
1. initialize a variable mid which will be the mid value of low and high, you can get using (low+mid)/2 but a better way to avoid overflow or underflow we should low + (high-low)/2
2. than check if nums[mid] is equal to our target value
3. [true] return with the mid index
4. [false]else if than check if nums[mid] is greater than target
5. [true] set high variable with mid -1
6. [false] else if than check if nums[mid] is smaller than target
7. [true] set low variable with mid + 1
return -1 index it means element is not present in array

Code

  def binary_search(nums, target):
      low = 0
      high = len(nums) - 1
      while low <= high:
  		mid = low + ((high - low) // 2)
  		if nums[mid] == target:
  			return mid
  		elif target < nums[mid]:
  			high = mid - 1
  		elif target > nums[mid]:
  			low = mid + 1
  	return -1

Time Complexity

O(*log*n) where n is the length of array

Space Complexity

O(1) no extra space is used

Recursive Solution of Binary Search

check base case (low is greater or equal to high) if true return -1 // it means target is not present in array
calculate mid index of low and high use mid = low+high/2 or mid = low+(high-low)/2
check if nums[mid] equal to target
[true] HURRAH! (we found the element in array) return mid
[False] check if nums[mid] smaller to target

Code

  def binary_search_rec(nums,target,low, high):
      if low>=high:
          return -1
      mid = low + (high-low)/2
      if nums[mid] == target:
          return mid
      if nums[mid] < target:
          return binary_search_rec(nums,target, low, mid-1)
      else:
          return binary_search_rec(nums,target, mid+1, low)

Time Complexity

O(*log*n) where n is the length of array

Space Complexity

O(*log*n) recursive stack space is used

Rotate An Array By N Elements

Problem Statement

We’re given an array of integers, nums. Rotate the array by n elements, where n is an integer:

For positive values of n, perform a right rotation.
For negative values of n, perform a left rotation. Make sure we make changes to the original array.

Example

Original Array

0	1	2	3	4	5	6	7	8	9
1	10	20	0	59	86	32	11	9	40

After Rotation if N=3

0	1	2	3	4	5	6	7	8	9
11	9	40	1	10	20	0	59	86	32

After Rotation from Original if N= -2

0	1	2	3	4	5	6	7	8	9
20	0	59	86	32	11	9	40	1	10

Sample Input

nums = [2, 13, 15, 1, 0, 4]
n = 2

Expected Output

[0, 4 ,2, 13, 15, 1]

Solution

Write a function to reverse Array from a index to b index
get length of array l
normalize N by taking modulus by length N=N%l
reverse array nums from 0 index to l-1 complete reverse
reverse array nums from 0 index to n-1
reverse array nums from n index to l-1
return nums

Code

def rotate_array(nums, n):
	def reverse_array(nums, s,e):
		while(s<e):
			nums[s],nums[e] = nums[e],nums[s]
			s+=1
			e-=1
		return nums

	l = len(nums)
	n = n%l
	nums = reverse_array(nums,0,l-1)
	nums = reverse_array(nums,0,n-1)
	nums = reverse_array(nums,n,l-1)
	return nums

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Rotated Binary Search

Problem Statement

We’re given a sorted integer array, array and an integer value, key. The array is rotated by some arbitrary number. Search the target in this array. If the target does not exist then return -1.

Example

0	1	2	3	4	5	6	7	8	9
13	14	20	0	2	3	5	7	8	11

Sample Input

array = [13, 14, 20, 0, 2, 3, 5, 7, 8, 11]
key = 20

Expected Output

Solution

initialize low = 0 and high = length of array -1
if low is greater than high return -1
start loop till low is less than or equal to high
1. initialize mid = low + (high-low)/2 we can also do mid = (low+high)/2 but this can cause overflow
2. check if array[mid] is equal to key if yes return mid
3. else check id array[low] is less than or equal to array[mid] if yes then
  1. check if key is greater than array[low] and key is less than array[mid] if yes then set high = mid-1
  2. else set low = mid+1
4. else
  1. check if key is greater than array[mid] and key is less than array[high] if yes then set low = mid+1
  2. else set high = mid-1
return -1

Code

def binary_search_rotated(nums, target):
    low = 0
    high = len(nums)-1
    if low>=high:
        return -1
    while low < high:
        mid = low + (high-low)//2
        if target == nums[mid]:
        return mid
        if nums[low] <= nums[mid]:
        if target < nums[mid] and target >= nums[low]:
            high = mid - 1
        else:
            low = mid + 1
        else:
        if target < nums[mid] and target <= nums[high]:
            low = mid - 1
        else:
            high = mid + 1
    return -1

Time Complexity

O(logn) where n is length of array

Space Complexity

O(1) no extra space is used

Smallest Common Number Between Three Arrays

Problem Statement

Given three integer arrays sorted in ascending order, find the smallest number that is common in all three arrays. For example, let's look at the below three arrays. Here 6 is the smallest number that's common in all the arrays.

Example

Input: [6, 7, 10, 25, 30, 63, 64], [0, 4, 5, 6, 7, 8, 50], [1, 6, 10, 14]
Output: 6

Solution

1. initialize i=0, j=0, k=0
2. start loop till i is less than length of array1 and j is less than length of array2 and k is less than length of array3
    1. check if array1[i] is equal to array2[j] and array2[j] is equal to array3[k] if yes then return array1[i]
    2. else check if array1[i] is less than array2[j] and array1[i] is less than array3[k] if yes then increment i
    3. else check if array2[j] is less than array1[i] and array2[j] is less than array3[k] if yes then increment j
    4. else increment k
3. return -1

Code

def find_least_common_number(a, b, c):
    i = 0
    j = 0
    k = 0
    while i < len(a) and j < len(b) and k < len(c):
        if a[i] == b[j] and b[j] == c[k]:
            return a[i]
        elif a[i] <= b[j] and a[i] <= c[k]:
            i += 1
        elif b[j] <= a[i] and b[j] <= c[k]:
            j += 1
        elif c[k] <= a[i] and c[k] <= b[j]:
            k += 1
    return -1

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Find Low and High Index of a key in sorted array

Problem Statement

Given a sorted array of integers, return the low and high index of the given key. Return -1 if not found. The array length can be in millions with lots of duplicates.

Example

Input: [1, 2, 5, 5, 5, 5, 5, 5, 5, 5, 20]
Output: 2, 9

Solution

LOW INDEX

initialize low = 0 and high = length of array -1
initialize mid = low + (high-low)/2 we can also do mid = (low+high)/2 but this can cause overflow
start loop till low <= high
1. check if array[mid] <= key if yes then set low = mid+1
2. else set high = mid-1
check if array[low] == key and low < length of array if yes then return low
else return -1

HIGH INDEX

initialize low = 0 and high = length of array -1
initialize mid = low + (high-low)/2 we can also do mid = (low+high)/2 but this can cause overflow
start loop till low <= high
1. check if array[mid] == key if yes then set high = mid-1
2. else set low = mid+1
check if array[high] is equal to key if yes then return high
else return -1

Code

def find_low_index(arr, key):
    low = 0
    high = len(arr) - 1
    mid = high // 2
    while low <= high:
        mid_elem = arr[mid]
        if mid_elem < key:
            low = mid + 1
        else:
            high = mid - 1
        mid = low + (high - low) // 2
    if low < len(arr) and arr[low] == key:
        return low
    return -1

def find_high_index(arr, key):
    low = 0
    high = len(arr) - 1
    mid = high // 2
    while low <= high:
        mid_elem = arr[mid]
        if mid_elem <= key:
            low = mid + 1
        else:
            high = mid - 1
        mid = low + (high - low) // 2
    if high == -1:
        return high
    if high < len(arr) and arr[high] == key:
        return high
    return -1

Time Complexity

O(logn) where n is length of array

Space Complexity

O(1) no extra space is used

Move all Zeros to the beging of the Array

Problem Statement

Given an integer array, move all elements containing '0' to the left while maintaining the order of other elements in the array.

Example

Input: [1,10,20,0,59,63,0,88,0]
Output: [0,0,0,1,10,20,59,63,88]

Solution

initialize write_index = length of array -1
start loop from length of array -1 till 0
1. check if array[i] != 0 if yes then set array[write_index] = array[i] and write_index -= 1
start loop from write_index till 0 and set array[i] = 0

Code

def move_zeros_to_left(nums):
  i = len(nums) - 1
  j = i
  while i >= 0:
    if nums[i]:
      nums[j]=nums[i]
      j-=1
    i-=1
  while j>=0:
    nums[j] = 0
    j-=1
  return nums

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Best Time to Buy and Sell Stock to Maximize Profit

Problem Statement

Given an array of numbers representing the daily stock prices of a company in chronological order, write a function that calculates the maximum profit you could have made from buying and selling that stock once. You must buy before you can sell it.

Example

Input: [9, 11, 8, 5, 7, 10]
Output: 5

Solution

check if array is None or length of array < 2 if yes then return None
initialize current_buy = array[0], global_sell = array[1], global_profit = global_sell - current_buy, current_profit = float('-inf')
start loop from 1 till length of array
1. set current_profit = array[i] - current_buy
2. check if current_profit > global_profit if yes then set global_profit = current_profit and global_sell = array[i]
3. check if current_buy > array[i] if yes then set current_buy = array[i]
return global_sell - global_profit, global_sell

Code

def find_buy_sell_stock_prices(array):
    if array == None or len(array) < 2:
        return None
    current_buy = array[0]
    global_sell = array[1]
    global_profit = global_sell - current_buy
    current_profit = float('-inf')
    for i in range(1, len(array)):
        current_profit = array[i] - current_buy
        if current_profit > global_profit:
            global_profit = current_profit
            global_sell = array[i]
        if current_buy > array[i]:
            current_buy = array[i]
    result = global_sell - global_profit, global_sell
    return result

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Merge An Array with Overlapping Intervals

Problem Statement

Given an array (list) of intervals as input where each interval has a start and end timestamps. Input array is sorted by starting timestamps. You are required to merge overlapping intervals and return output array (list).

Example

Input: [(1, 5), (3, 7), (4, 6), (6, 8), (10, 12), (11, 15)]
Output: [(1, 8), (10, 15)]

Solution

initialize merged = []
start loop from 1 till length of array
1. check if array[i][0] <= merged[-1][1] if yes then set merged[-1][1] = max(merged[-1][1], array[i][1])
2. else append array[i] to merged
return merged

Code

def merge_intervals(v):
  result = [v[0]]
  j = 1
  for i in range(1,len(v)):
    if result[j-1][2] >= v[i][0]:
      if v[i][1] > result[j-1][1]:
        result[j-1][1] = v[i][0]

    else:
      result.append(v[i])
      j+=1
  return result

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Find Pair With Given Sum in Array

Problem Statement

Given an unsorted array of integers, find a pair with given sum in it.

Example

Input: [8, 7, 2, 5, 3, 1]
Sum: 10
Output: [0, 2] or [1, 4]

Solution

initialize hash_map = {}
start loop from 0 till length of array
1. check if array[i] in hash_map if yes then return True
2. else hash_map[sum - array[i]] = i
return False

Code

def find_sum_of_two(A, val):
  hash_map = {}
  for i in range(len(A)):
    if A[i] in hash_map:
      return True
    else:
      hash_map[val - A[i]] = A[i]
  return False

Time Complexity

O(n) where n is length of array

Space Complexity

O(n) where n is length of array for hash_map

Squares Of a Sorted Array

Problem Statement

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Solution

initialize result = []
initialize left = 0, right = len(array) - 1
start loop from right till left
1. check if abs(array[left]) > abs(array[right]) if yes then result.append(array[left] * array[left]) and left += 1
2. else result.append(array[right] * array[right]) and right -= 1
return result[::-1] to reverse the array

Code

def sortedSquares(nums):
  result = []
  left = 0
  right = len(nums) - 1
  while left <= right:
    if abs(nums[left]) > abs(nums[right]):
      result.append(nums[left] * nums[left])
      left += 1
    else:
      result.append(nums[right] * nums[right])
      right -= 1
  return result[::-1]

Time Complexity

O(n) where n is length of array

Space Complexity

O(n) where n is length of array for result

Container With Most Water

Problem Statement

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Example

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Solution

initialize left = 0, right = len(array) - 1
initialize max_area = 0
start loop from left till right
1. check if array[left] < array[right] if yes then max_area = max(max_area, array[left] * (right - left)) and left += 1
2. else max_area = max(max_area, array[right] * (right - left)) and right -= 1
return max_area

Code

def max_water_area_container(height):
    i = 0
    j = len(height)-1
    max_water = 0
    while(i<j):
        hi,hj= height[i],height[j]
        container = min(hi,hj)* (j-i)
        if max_water < container:
            max_water = container
        if hi < hj:
            i+=1
        else:
            j-=1
    return max_water

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Quick Sort Algorithm

Problem Statement

Given an array of integers, sort the array in ascending order using the Quick Sort algorithm.

Example

Input: [8, 7, 2, 5, 3, 1]
Output: [1, 2, 3, 5, 7, 8]

Solution

Partition

initialize pivot_value = array[low]
initialize i = low, j = high
start loop till i < j
1. start loop till i <= j and array[i] <= pivot_value if yes then i += 1
2. start loop till array[j] > pivot_value if yes then j -= 1
3. check if i < j if yes then array[i], array[j] = array[j], array[i]
array[low], array[j] = array[j], pivot_value
return j

Quick Sort Helper

check if low < high if yes then
1. pivot_index = partition(array, low, high)
2. quick_sort_helper(array, low, pivot_index-1)
3. quick_sort_helper(array, pivot_index+1, high)

Quick Sort

quick_sort_helper(array, 0, len(array)-1)
return array

Code

def partition(nums, low, high):
    pivot_value = nums[low]
    i = low
    j = high
    while i<j:
        while i <= j and nums[i] <= pivot_value:
            i += 1
        while nums[j] > pivot_value:
            j-=1

        if i<j:
            nums[i], nums[j] = nums[j], nums[i]
        
    nums[low], nums[j] = nums[j], pivot_value
    
    return j

def quick_sort_helper(nums, low, high):
    if low < high:
        pivot_index = partition(nums, low, high)
        quick_sort_helper(nums, low, pivot_index-1)
        quick_sort_helper(nums, pivot_index+1, high)

def quick_sort(nums):
    quick_sort_helper(nums, 0, len(nums)-1)
    return nums

Time Complexity

O(nlogn) where n is length of array

Space Complexity

O(logn) where n is length of array for recursion stack

Sort Colors

Problem Statement

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

Example

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Solution

initialize low = 0, mid = 0, high = len(array) - 1
start loop till mid <= high
1. check if array[mid] == 0 if yes then array[low], array[mid] = array[mid], array[low] and low += 1
2. check if array[mid] == 1 if yes then mid += 1
3. check if array[mid] == 2 if yes then array[mid], array[high] = array[high], array[mid] and high -= 1
return array

Code

def sort_colors(nums):
    low = 0
    mid = 0
    high = len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
    return nums

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Arrange The Largest Number

Problem Statement

Given a list of non negative integers, arrange them in such a manner that they form the largest number possible.The result is going to be very large, hence return the result in the form of a string.

Example

Input: [3, 30, 34, 5, 9]
Output: 9534330

Solution

initialize array = [str(i) for i in array]
sort the array using lambda function
return ''.join(array)

Code

class LargerNumKey(str):
  def __lt__(x,y):
    return x+y > y+x

def largest_number(nums):
  mapStr = map(str, nums)
  mapStr = sorted(mapStr,key=LargerNumKey)
  largest = ''.join(mapStr)
  return '0' if largest[0] == '0' else largest

Time Complexity

O(nlogn) where n is length of array

Space Complexity

O(n) where n is length of array for extra space used for storing string

Shuffle Array

Incomplete

First Missing Positive Integer

Problem Statement

Given an unsorted integer array nums, find the smallest missing positive integer.

Example

Input: nums = [1,2,0]
Output: 3

Solution

initialize i = 0
start loop till i < len(array)
1. check if array[i] > 0 and array[i] <= len(array) and array[i] != array[array[i]-1] if yes then array[array[i]-1], array[i] = array[i], array[array[i]-1] else i += 1
start loop till i < len(array)
1. check if array[i] != i+1 if yes then return i+1 else i += 1
return len(array)+1

Code

def first_missing_positive(nums):
    i = 0
    while i < len(nums):
        if nums[i] > 0 and nums[i] <= len(nums) and nums[i] != nums[nums[i]-1]:
            nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        else:
            i += 1
    i = 0
    while i < len(nums):
        if nums[i] != i+1:
            return i+1
        else:
            i += 1
    return len(nums)+1

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Minimum Size Subarray Sum

Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

Solution

initialize left = 0, sum1 = 0, result = float('inf')
start loop till i < len(array)
1. sum1 += array[i]
2. start loop till sum1 >= target
  1. result = min(result,(i+1) - left)
  2. sum1 -= array[left]
  3. left += 1
check if result == float('inf') if yes then return 0 else return result

Code

def min_sub_array_len(target, nums):
	left = 0
	sum1 = 0
	result = float('inf')
	for i in range(len(nums)):
		sum1 += nums[i]
		while sum1>= target:
			result = min(result,(i+1) - left)
			sum1 -= nums[left]
			left+=1
	if result == float('inf'):
		return 0
	return result

Time Complexity

O(n) where n is length of array

Space Complexity

O(1) no extra space is used

Next Element Greater Than Subset

Problem Statement

Given an array, find the next greater element G[i] for every element A[i] in the array. The Next greater Element for an element A[i] is the first greater element on the right side of A[i] in array. More formally,

Example

Input

    nums1 = [4,1,2]
    nums2 = [1,3,4,2].

Output

    [-1, 3, -1]

Solution

initialize stack = []
initialize hash_map = {}
start loop from 0 till length of array2
1. check if stack is not empty and array2[i] > stack[-1] if yes then hash_map[stack.pop()] = array2[i]
2. append array2[i] to stack
start loop from 0 till length of array1
1. check if array1[i] in hash_map if yes then array1[i] = hash_map[array1[i]] else array1[i] = -1
return array1

Code

def next_greater_element(nums1, nums2):
    stack = []
    hash_map = {}
    for i in range(len(nums2)):
        while stack and nums2[i] > stack[-1]:
            hash_map[stack.pop()] = nums2[i]
        stack.append(nums2[i])
    for i in range(len(nums1)):
        if nums1[i] in hash_map:
            nums1[i] = hash_map[nums1[i]]
        else:
            nums1[i] = -1
    return nums1

Time Complexity

O(n) where n is length of array

Space Complexity

O(n) where n is length of array for stack and hash_map

Product of All Elements Except Itself in an Array

Problem Statement

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

Example

Input: [1, 2, 3, 4, 5]
Output: [120, 60, 40, 30, 24]

Solution

initialize result = [1] * len(array)
initialize left = [1] * len(array)
initialize right = [1] * len(array)
start loop from 1 till length of array
1. left[i] = left[i-1] * array[i-1]
start loop from length of array - 2 till -1
1. right[i] = right[i+1] * array[i+1]
start loop from 0 till length of array
1. result[i] = left[i] * right[i]
return result

Code

def product_except_self(nums):
    result = [1] * len(nums)
    left = [1] * len(nums)
    right = [1] * len(nums)
    for i in range(1, len(nums)):
        left[i] = left[i-1] * nums[i-1]
    for i in range(len(nums)-2, -1, -1):
        right[i] = right[i+1] * nums[i+1]
    for i in range(len(nums)):
        result[i] = left[i] * right[i]
    return result

Time Complexity

O(n) where n is length of array

Space Complexity

O(n) where n is length of array for left, right and result

Linked-List

Implementation of Single Linked List

Problem Statement

Psuedo Code

class Node
    private:
        <variable> data
        <Pointer Node> next
    public:
        <function> constructor(data):
            mine.data = data
            mine.next = NULL

class SingleLinkedList
    private:
        <Pointer Node> head
    public:
        
        <function> constructor():
            head = NULL
        
        
        <function> constructor(<variable> data):
            head = Node(data)
        
        <function> constructor(<Pointer Node> head):
            <Pointer Node> ptr = head
            mine.head = NULL
            while ptr != NULL:
                mine.insert_at_tail(ptr.data)
                ptr = ptr.next

        <function> insert_at_head(<variable> data):
            <Pointer Node> new_node = Node(data)
            if head == NULL:
                head = new_node
            else:
                new_node.next = head
                head = new_node    

        <function> insert_at_tail(<variable> data):
            <Pointer Node> new_node = Node(data)
            if head == NULL:
                head = new_node
            else:
                <Pointer Node> ptr = head
                while ptr.next != NULL:
                    ptr = ptr.next
                ptr.next = new_node

        <function> insert_at_position(<variable> data, <variable> position):
            <Pointer Node> new_node = Node(data)
            if head == NULL:
                head = new_node
            else:
                <Pointer Node> ptr = head
                <Pointer Node> prev = NULL
                <variable> count = 0
                while ptr != NULL and count < position:
                    prev = ptr
                    ptr = ptr.next
                    count += 1
                prev.next = new_node
                new_node.next = ptr
        
        <function> delete_at_head():
            if head == NULL:
                return
            else:
                <Pointer Node> ptr = head
                head = head.next
                ptr.next = NULL
                delete ptr

        <function> delete_at_tail():
            if head == NULL:
                return
            else:
                <Pointer Node> ptr = head
                <Pointer Node> prev = NULL
                while ptr.next != NULL:
                    prev = ptr
                    ptr = ptr.next
                prev.next = NULL
                delete ptr

        <function> delete_at_position(<variable> position):
            if head == NULL:
                return
            else:
                <Pointer Node> ptr = head
                <Pointer Node> prev = NULL
                <variable> count = 0
                while ptr != NULL and count < position:
                    prev = ptr
                    ptr = ptr.next
                    count += 1
                prev.next = ptr.next
                ptr.next = NULL
                delete ptr
        
        <function> delete_by_value(<variable> data):
            if head == NULL:
                return
            else:
                <Pointer Node> ptr = head
                <Pointer Node> prev = NULL
                while ptr != NULL and ptr.data != data:
                    prev = ptr
                    ptr = ptr.next
                if ptr == NULL:
                    return
                else:
                    prev.next = ptr.next
                    ptr.next = NULL
                    delete ptr  
        

        <function> search(<variable> data):
            if head == NULL:
                return False
            else:
                <Pointer Node> ptr = head
                while ptr != NULL and ptr.data != data:
                    ptr = ptr.next
                if ptr == NULL:
                    return False
                else:
                    return True

Single Linked List Python Code

Reverse a Single Linked List

Problem Statement

Given a singly linked list, write a function to reverse the linked list.

Example

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Solution

initialize prev = NULL, curr = head, next = NULL
start loop till curr != NULL
1. next = curr.next
2. curr.next = prev
3. prev = curr
4. curr = next
head = prev
return head

Code

def reverseLinkedList(head):
    if head is None or head.next is None:
        return head

    prev = None
    curr = head
    next = None

    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    head = prev
    return head

Node* reverseLinkedList(Node* head){
    if (head == NULL || head->next == NULL)
        return head;
    
    Node *prev = NULL;
    Node *curr = head;
    Node *next = NULL;

    while(curr != NULL){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;
}

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Remove Duplicate From Linked List

Problem Statement

Given a linked list, delete all duplicates such that each element appear only once. Linked List can be unSorted

Example

Input: 1->2->3->3->2->1->NULL
Output: 1->2->3->NULL

Solution

initialize ptr = head
initialize hash_set = set()
add ptr.data to hash_set
while ptr.next != NULL
1. check if ptr.next.data in hash_set if yes then ptr.next = ptr.next.next
2. else hash_set.add(ptr.next.data) and ptr = ptr.next
return head

Code

def removeDuplicates(head):
    if head is None or head.next is None:
        return head
    
    curr = head
    hashset = set()
    hashset.add(curr.data)
    while curr.next is not None:
        if curr.next.data in hashset:
            curr.next = curr.next.next
        else:
            hashset.add(curr.next.data)
            curr = curr.next
    return head0

Node* removeDuplicates(Node* head){
    if (head == NULL || head->next == NULL)
        return head;
    
    Node *curr = head;
    unordered_set<int> hashset;
    hashset.insert(curr->data);
    while(curr->next != NULL){
        if (hashset.find(curr->next->data) != hashset.end()){
            curr->next = curr->next->next;
        }
        else{
            hashset.insert(curr->next->data);
            curr = curr->next;
        }
    }
    return head;
}

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(n) used for hashset

Delete All Occurrences of a Given Key in a Linked List

Problem Statement

Given a singly linked list, delete all occurrences of a given key in it. Linked List can be unSorted

Example

Input: 1->2->3->3->2->1->NULL, key = 2
Output: 1->3->3->1->NULL

Solution

if head == NULL return NULL
initialize curr = head, prev = NULL
while curr != NULL
1. if curr.data == key
  1. if prev == NULL then head = curr.next and curr = head
  2. else prev.next = curr.next and curr = curr.next
2. else prev = curr and curr = curr.next
return head

Code

def deleteAllOccurences(head, key):
    if head is None:
        return None
    curr = head
    prev = None
    while curr is not None:
        if curr.value == key:
            if prev is None:
                head = curr.next
                curr = head
            else:
                prev.next = curr.next
                curr = curr.next
        else:
            prev = curr
            curr = curr.next
    return head

Node* deleteAllOccurences(Node * Head, int key){
    if (Head == NULL)
        return;
    Node *curr = Head;
    Node *prev = NULL;
    while(curr != NULL){
        if (curr->data == key){
            if (prev == NULL){
                Head = curr->next;
                curr = Head;
            }
            else{
                prev->next = curr->next;
                curr = curr->next;
            }
        }
        else{
            prev = curr;
            curr = curr->next;
        }
    }
    return Head;
}

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Insertion Sort on Linked List

Problem Statement

Given a linked list, sort it using insertion sort.

Example

Input: 1->3->2->4->5->1->NULL
Output: 1->1->2->3->4->5->NULL

Solution

sorted_insert (head,node)

if node == NULL return head
if head == NULL or node.value <= head.value then node.next = head and return node
initialize curr = head
while curr.next != NULL and curr.next.value < node.value then
1. curr = curr.next
node.next = curr.next and curr.next = node
return head

insertion_sort(head)

if head == NULL return NULL
initialize sorted_list = NULL, curr = head
while curr != NULL
1. initialize temp = curr.next
2. sorted_list = sorted_insert(sorted_list, curr)
3. curr = temp
return sorted_list

Code

def sorted_insert(head, node):
    if node is None:
        return head
    if head is None or node.value <= head.value:
        node.next = head
        return node
    curr = head
    while curr.next is not None and curr.next.value < node.value:
        curr = curr.next
    node.next = curr.next
    curr.next = node
    return head

def insertion_sort(head):
    if head is None:
        return None
    sorted_list = None
    curr = head
    while curr is not None:
        temp = curr.next
        sorted_list = sorted_insert(sorted_list, curr)
        curr = temp
    return sorted_list

Time Complexity

O(n^2) where n is length of linked list

Space Complexity

O(1) no extra space is used

Intersection of Linked Lists

Problem Statement

Given two singly linked lists of size N and M, write a program to get the point where two linked lists intersect each other.

Solution WithOut Using Extra Space

initialize l1 = length(head1), l2 = length(head2)
if l1 > l2 then return intersect(head2, head1)
initialize diff = l2 - l1, curr1 = head1, curr2 = head2
for i = 0 to diff do curr2 = curr2.next
while curr1 != NULL and curr2 != NULL do
1. if curr1 == curr2 then return curr1
2. curr1 = curr1.next, curr2 = curr2.next
return NULL

Code WithOut Using Extra Space

def intersect(head1, head2):
    l1 = length(head1)
    l2 = length(head2)
    if l1 > l2:
        return intersect(head2, head1)
    diff = l2 - l1
    curr1 = head1
    curr2 = head2
    for i in range(diff):
        curr2 = curr2.next
    while curr1 is not None and curr2 is not None:
        if curr1 == curr2:
            return curr1
        curr1 = curr1.next
        curr2 = curr2.next
    return None

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Solution With Extra Space

initialize hash_set = set(), curr = head1
while curr != NULL do hash_set.add(curr), curr = curr.next
initialize curr = head2
while curr != NULL and curr not in hash_set do curr = curr.next
return curr

Code With Extra Space

def intersect_using_extra_space(head1,head2):
    hash_set = set()
    curr = head1
    while curr is not None:
        hash_set.add(curr)
        curr = curr.next
    curr = head2
    while curr is not None and curr not in hash_set:
        curr = curr.next
    return curr

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(n) used for hashset

Nth Node from End of Linked List

Problem Statement

Given a linked list consisting of L nodes and given a number N. The task is to find the Nth node from the end of the linked list.

Example

Input: 1->2->3->4->5, N = 2
Output: 4

Solution

initialize ptr = head
while n > 0 and ptr != NULL do ptr = ptr.next, n -= 1
if ptr == NULL and n > 0 then return NULL
while ptr != NULL do ptr = ptr.next, head = head.next
return head

Code

def find_nth_from_end(head,n):
    ptr = head
    while n>0 and ptr is not None:
        ptr = ptr.next
        n-=1
    if ptr is None and n>0:
        return None
    while ptr is not None:
        ptr = ptr.next
        head = head.next
    return head

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Swap Nth Node with Head

Problem Statement

Given a singly Linked List, write a function to swap the Nth node from the beginning with head

Example

Input: 1->2->3->4->5, N = 4
Output: 4->2->3->1->5

Solution

initialize prev = head, curr = head
while n > 0 and curr.next != NULL do prev = curr, curr = curr.next, n -= 1
if n == 0 and prev != NULL then swap(prev, head)
return head

Code

def swap_nth_node(head, n):
    prev = head
    curr = head
    while n>0 and curr.next is not None:
        prev = curr
        curr = curr.next
        n-=1
    if n==0 and prev is not None:   
        head.value, prev.value = prev.value, head.value
    return head

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Merge Two Sorted Linked Lists

Problem Statement

Given two sorted linked lists consisting of N and M nodes respectively. The task is to merge both of the list (in-place) and return head of the merged list.

Example

Input: 1->3->5->7->9, 2->4->6->8
Output: 1->2->3->4->5->6->7->8->9

Solution

if head1 == NULL then return head2
if head2 == NULL then return head1
if head1.value < head2.value then head1.next = merge_sorted(head1.next, head2), return head1
else head2.next = merge_sorted(head1, head2.next), return head2

Code

def merge_sorted(head1, head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    if head1.value < head2.value:
        head1.next = merge_sorted(head1.next, head2)
        return head1
    else:
        head2.next = merge_sorted(head1, head2.next)
        return head2

Time Complexity

O(n+m) where n and m are length of linked lists

Space Complexity

O(1) no extra space is used

Merge Sort on Linked List

Problem Statement

Given Pointer/Reference to the head of a doubly linked list of N nodes, the task is to Sort the given doubly linked list using Merge Sort in both non-decreasing and non-increasing order.

Example

Input: 8->4->2->5
Output: 2->4->5->8

Solution

get_middle(head)

check if head == NULL then return head
initialize slow = head, fast = head
while fast.next != NULL and fast.next.next != NULL do slow = slow.next, fast = fast.next.next
return slow

merge_sort(head)

check if head == NULL or head.next == NULL then return head
initialize mid = get_mid(head), next_to_mid = mid.next, mid.next = NULL
initialize left = merge_sort(head), right = merge_sort(next_to_mid)
initialize sorted_list = merge_sorted(left, right)
return sorted_list

Code

def get_middle(head):
    if head is None:
        return head
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

def merge_sort(head):
    if head is None or head.next is None:
        return head
    mid = get_mid(head)
    next_to_mid = mid.next
    mid.next = None
    left = merge_sort(head)
    right = merge_sort(next_to_mid)
    sorted_list = merge_sorted(left, right)
    return sorted_list

Time Complexity

O(nlogn) where n is length of linked list

Space Complexity

O(1) no extra space is used

Reverse Even Nodes In A Linked List

Problem Statement

Given a singly linked list, reverse nodes at even indices (starting at 1).

Example

Input: 1->2->3->4->5->6->NULL
Output: 1->6->3->4->5->2->NULL

Solution

odd_and_even_nodes(head)

initialize curr = head, l_even = NULL
while curr != NULL and curr.next != NULL do even = curr.next, curr.next = even.next, even.next = l_even, l_even = even, curr = curr.next
return head, l_even

merge_alternate(odd, even)

if odd == NULL then return even
if even == NULL then return odd
initialize head = odd
while odd.next != NULL do temp = odd.next, odd.next = even, even = even.next, odd.next.next = temp, odd = temp
odd.next = even
return head

reverse_even_nodes(head)

initialize odd,even = odd_and_even_nodes(head)
return merge_alternate(odd, even)

Code

def odd_and_even_nodes(head):
    curr = head
    l_even = None
    while curr and curr.next:
        even = curr.next
        curr.next = even.next
        even.next = l_even
        l_even = even
        curr = curr.next
    return head, l_even

def merge_alternate(odd, even):
    if not odd:
        return even
    if not even:
        return odd
    head = odd
    while odd.next:
        temp = odd.next
        odd.next = even
        even = even.next
        odd.next.next = temp
        odd = temp
    odd.next = even
    return head

def reverse_even_nodes(head):
    odd,even = odd_and_even_nodes(head)
    return merge_alternate(odd, even)

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Rotate List

Problem Statement

Given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer. For example, if the given linked list is 10->20->30->40->50->60 and k is 4, the list should be modified to 50->60->10->20->30->40. Assume that k is smaller than the count of nodes in linked list.

Example

Input: 1->2->3->4->5->NULL, k = 2
Output: 3->4->5->1->2->NULL

Solution

initialize n = n % len(head)
if n == 0 or head == NULL then return head
initialize curr = head
for i in range(n-1) do curr = curr.next
initialize new_head = curr.next
curr.next = NULL
curr = new_head
while curr.next != NULL do curr = curr.next
curr.next = head
return new_head

Code

def rotate_list(head,n):
    n = n % len(head)
    if n == 0 or not head:
        return head
    curr = head
    for i in range(n-1):
        curr = curr.next
    new_head = curr.next
    curr.next = None
    curr = new_head
    while curr.next:
        curr = curr.next
    curr.next = head
    return new_head

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Reorder List

Problem Statement

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes' values. For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

Example

Input: 1->2->3->4->NULL
Output: 1->4->2->3->NULL

Solution

halves(head)

if head == NULL then return NULL, NULL
initialize slow = head, fast = head.next
while fast != NULL and fast.next != NULL do slow = slow.next, fast = fast.next.next
initialize head2 = slow.next
slow.next = NULL
initialize rev_head2 = NULL
while head2 != NULL do temp = head2.next, head2.next = rev_head2, rev_head2 = head2, head2 = temp
head2 = rev_head2
return head, head2

merge_alternate(head1, head2)

Explained Above in Odd and Even Nodes Problem Link

reorder_list(head)

initialize head1, head2 = halves(head)
return merge_alternate(head1, head2)

Code

def halves(head):
    if not head:
        return None, None
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    head2 = slow.next
    slow.next = None
    rev_head2 = None
    while head2:
        temp = head2.next
        head2.next = rev_head2
        rev_head2 = head2
        head2 = temp
    head2 = rev_head2
    return head, head2

def merge_alternate(head1, head2):
    if not head1:
        return head2
    if not head2:
        return head1
    head = head1
    while head1.next:
        temp = head1.next
        head1.next = head2
        head2 = head2.next
        head1.next.next = temp
        head1 = temp
    head1.next = head2
    return head

def reorder_list(head):
    head1, head2 = halves(head)
    return merge_alternate(head1, head2)

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Add Two Integers Represented as Linked Lists

Problem Statement

Given two numbers represented by two lists, write a function that returns sum list. The sum list is list representation of addition of two input numbers. Suppose the digits are stored in forward order. In that case, repeat the above problem. Given two numbers represented by two lists, write a function that returns sum list. The sum list is list representation of addition of two input numbers.

Example

Input:
  First List: 5->6->3  // represents number 365
  Second List: 8->4->2 //  represents number 248
Output:
    Resultant list: 3->1->6  // represents number 613

Solution

initialize carry = 0
initialize head = None
while int1 != NULL or int2 != NULL or carry != 0 do
1. initialize sum = carry
2. if int1 != NULL then sum += int1.value, int1 = int1.next
3. if int2 != NULL then sum += int2.value, int2 = int2.next
4. initialize digit = sum % 10
5. carry = sum // 10
6. if head == NULL then head = LinkedListNode(digit), tail = head
7. else tail.next = LinkedListNode(digit), tail = tail.next
return head

Code

def add_integers(int1,int2):
    carry = 0
    head = None
    while int1 or int2 or carry:
        sum = carry
        if int1:
            sum += int1.value
            int1 = int1.next
        if int2:
            sum += int2.value
            int2 = int2.next
        digit = sum % 10
        carry = sum // 10
        if not head:
            head = LinkedListNode(digit)
            tail = head
        else:
            tail.next = LinkedListNode(digit)
            tail = tail.next
    return head

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(1) no extra space is used

Deep Copy

Problem Statement

Given a linked list. We have to copy the given linked list such that change in one copy will not reflect in other.

Example

Input : 1->2->3->4->5
Output : 1`->2`->3`->4`->5`

Solution

initialize deep_head = None, deep_tail = None, curr = head
while curr != NULL do
1. if deep_head == NULL then deep_head = LinkedListNode(curr.value), deep_tail = deep_head
2. else deep_tail.next = LinkedListNode(curr.value), deep_tail = deep_tail.next
3. curr = curr.next
return deep_head

Code

def deep_copy_list(head):
    deep_head = None
    deep_tail = None
    curr = head
    while curr:
        if not deep_head:
            deep_head = LinkedListNode(curr.value)
            deep_tail = deep_head
        else:
            deep_tail.next = LinkedListNode(curr.value)
            deep_tail = deep_tail.next
        curr = curr.next
    return deep_head

Time Complexity

O(n) where n is length of linked list

Space Complexity

O(n) where n is length of linked list for new Linked List.

Name		Name	Last commit message	Last commit date
Latest commit History 89 Commits
.github		.github
python		python
Array.md		Array.md
LinkedList.md		LinkedList.md
README.md		README.md

salman486/problem-solving

Folders and files

Latest commit

History

Repository files navigation

Problem Solving

Table of Contents

Array

Binary Search On Sorted Array

Iterative Solution Of Binary Search

Code

Time Complexity

Space Complexity

Recursive Solution of Binary Search

Code

Time Complexity

Space Complexity

Rotate An Array By N Elements

Problem Statement

Example

Solution

Code

Time Complexity

Space Complexity

Rotated Binary Search

Problem Statement

Example

Sample Input

Expected Output

Solution

Code

Time Complexity

Space Complexity

Smallest Common Number Between Three Arrays

Problem Statement

Example

Solution

Code

Time Complexity

Space Complexity

Find Low and High Index of a key in sorted array

Problem Statement

Example

Solution

Code

Time Complexity

Space Complexity

Move all Zeros to the beging of the Array

Problem Statement

Example

Solution

Code

Time Complexity

Space Complexity

Best Time to Buy and Sell Stock to Maximize Profit

Problem Statement

Example

Solution

Code

Time Complexity

Space Complexity

Merge An Array with Overlapping Intervals

Problem Statement

Example

Solution

Code

Time Complexity

Space Complexity

Find Pair With Given Sum in Array

Problem Statement

Example

Solution

Code

Time Complexity

Space Complexity

Squares Of a Sorted Array

Problem Statement

Example

Solution

Code