DEV Community: Rishab Trivedi

Sliding Window || Python || Data Structures and Algorithms

Rishab Trivedi — Sun, 02 Feb 2025 03:07:26 +0000

What is Sliding Window Technique ?

Sliding Window Technique is a method where we define a window or range in the input data (arrays or strings) and then move that window across the data to perform some operation within the window.

This technique is commonly used in algorithms like finding subarrays with a specific sum, finding the longest substring with unique characters, or solving problems that require a fixed-size window to process elements efficiently.

Two Types of Sliding Window-

1. Fixed Size Sliding Window - In this, the size of the window is fixed, and we move the window across the array.

2. Variable Size Sliding Window - In this, we increment the right pointer by one in each iteration, and we move the left pointer only when the condition is not met. We continue moving the left pointer until the condition is met again or it reaches the right pointer.

When should we use sliding window?

Whenever we see a problem where we need to calculate maximum or minimum of a subarray or any operation related to subarray then There is a high chance a sliding window can be used in it.

General template for Sliding Window -

function fn(arr):
    left = 0
    for (int right = 0; right < arr.length; right++):
        Do some logic to "add" element at arr[right] to window

        while WINDOW_IS_INVALID:
            Do some logic to "remove" element at arr[left] from window
            left++

        Do some logic to update the answer

Example - Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Test Case 1:

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

Output: 2

Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Test Case 2:

Input: target = 4, nums = [1,4,4]

Output: 1

Test Case 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]

Output: 0

Brute Force - The Brute Force Approach to solve this problem is to iterate from left to right for each element. Then calculate the subarray sum for all the elements between our left and right pointer.

So the time complexity will be O(n) * O(n(n+1) /2 ) = O(n3)

Sliding Window Approach -

Code -

Algorithm -

Initialize 2 pointers left and right and Two more variables one for calculating current sum and and one for size of minimum window.
Our window size will always be (right - left + 1) , as arrays starting index starts from 0.
Now increment the right pointer in each iteration.
In each iteration check if the current sum of the window exceeds the target then we have to decrease the size of our window.
Increment the left pointer until the size of the window is correct as per the condition.
During this calculate the size of the minimum window as we want to calculate the minimum size window.
At Last if the min Window variable has changed the return the original value otherwise return 0.

Time Complexity - O(n) as for the worst case we are iterating through the array elements at most twice.

Simplifying O(2n) to O(n)

Space Complexity - O(1)

By using sliding window algorithm we reduced the time complexity from O(n3) to O(n).

Stack and Queue || Python || Data Structures and Algorithms

Rishab Trivedi — Sat, 21 Dec 2024 09:31:19 +0000

Stack

Stack - It is a storage container which supports retrieval by last-in, first-out ( LIFO) order. Stacks are probably the right container to use when retrieval order doesn’t matter at all, such as when processing batch jobs.

For example, consider a stack of plates used in cafeterias: the order in which plates are removed from the stack is the reverse of the order in which they were added, as only the top plate is accessible.

The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP.

Push (x,s): Insert item x at the top of stack s.

Pop(s) : Return (and remove) the top item of stack s.

Food inserted into my refrigerator usually exits the same way, despite the incentive of expiration dates. Algorithmically, LIFO tends to happen in the course of executing recursive algorithms.

Applications of Stack -

Function calls: Used to manage function execution and recursion.
Undo operations: Tracks changes in editors for "Undo/Redo."
Browser history: Stores visited pages for backtracking.
Expression parsing: Evaluates and converts mathematical expressions.
Syntax validation: Matches parentheses or tags in code.
Memory management: Manages call stacks during program execution.
DFS: Implements Depth-First Search in graph algorithms.

Implement Stack Using Array -

push() - Insert an element into the stack
pop() - Remove an element from the stack
top() - Returns the top element of the stack.
isEmpty() - Returns true if the stack is empty else false.

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

Queue

Queue - It is a storage container which supports retrieval by first-in, first-out (FIFO) order. We call the INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE. Like the stack operation POP, DEQUEUE takes no element argument. Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is predefined.

Enqueue(x,q): Insert item x at the back of queue q.

Dequeue(q): Return (and remove) the front item from queue q.

The queue has a head and a tail.

When an element is enqueued, it takes its place at the tail of the queue, just as a newly arriving customer takes a place at the end of the line.
The element dequeued is always the one at the head of the queue, like the customer at the head of the line, who has waited the longest.

Applications of Queue -

Task scheduling: Manages CPU processes and jobs in order.
BFS: Implements Breadth-First Search in graphs.
Print queues: Handles print jobs sequentially.
Network routing: Buffers data packets for transmission.
Call centers: Manages customer calls in waiting order.
Streaming: Buffers video or audio streams in real-time.
Input events: Processes keyboard and mouse inputs in GUI systems.

Implement Queue Using Array-

enqueue() – Insertion of elements to the queue.
dequeue() – Removal of elements from the queue.
peek() or front()- Acquires the data element available at the front node of the queue without deleting it.
isEmpty() – Checks if the queue is empty.

class MyQueue:
    def __init__(self):
        # Store elements
        self.queue = []
        # A pointer to indicate the start position
        self.p_start = 0

    def enQueue(self, x):
        #Insert an element into the queue. 
        self.queue.append(x)
        return True # Return True if the operation is successful

    def deQueue(self):
        #Delete an element from the queue. 
        if self.isEmpty():
            return False
        self.p_start += 1
        return True #Return True if the operation is successful

    def Front(self):
        #Get the front item from the queue.
        if not self.isEmpty():
            return self.queue[self.p_start]
        return None  # Return None if the queue is empty

    def isEmpty(self):
        #Checks whether the queue is empty or not
        return self.p_start >= len(self.queue)

Implement Queue using Stacks -

push(x) - Move all elements from stack1 to stack 2 to reverse their order and then and again move all elements back from stack2 to stack 1.
pop() - Removes the element from the front of the queue and returns it
peek() - Returns the element at the front of the queue
empty() - Returns true if the queue is empty, false otherwise

class MyQueue:

    def __init__(self):
        self.stack_1 = []  # Main stack for enqueue operations
        self.stack_2 = []  # Temporary stack for dequeue operations
        self.front = None

    # Pushes element x to the back of the queue.
    def push(self, x):

        # Move all elements from stack1 to stack 2 to reverse their order
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        self.stack_2.append(x)

        # Move all elements back from stack2 to stack 1 as a queue
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())

    # Removes the element from the front of the queue and returns it
    def pop(self):
        return self.stack_1.pop()

    # Returns the element at the front of the queue
    def peek(self):
        return self.stack_1[-1]

    # Returns true if the queue is empty, false otherwise
    def empty(self):
        return not self.stack_1

Implement Stack using Queues -

push(x) - Add new element to second queue, then move all elements from queue 1 to queue 2 to maintain stack order (LIFO) and Swap the queues.
pop() - Removes the element on the top of the stack and returns it
peek or top() - Returns the element at the front of the queue
empty() - Returns true if the queue is empty, false otherwise

class MyStack:

    def __init__(self):
        # Initialize two queues for stack operations
        self.queue1 = [] # Main queue to hold elements
        self.queue2 = [] # Temporary queue used during push

    # Pushes element x to the top of the stack
    def push(self, x: int) -> None:

        # Add new element to second queue
        self.queue2.append(x)

        # Move all elements from queue 1 to queue 2 to maintain stack order (LIFO)
        while len(self.queue1) > 0:
            self.queue2.append(self.queue1.pop(0))

        # Swap the queues
        self.queue1, self.queue2 = self.queue2, self.queue1

    # Removes the element on the top of the stack and returns it
    def pop(self) -> int:
        return self.queue1.pop(0)

    # Returns the element on the top of the stack
    def top(self) -> int:
        return self.queue1[0]

    # Returns true if the stack is empty, false otherwise.
    def empty(self) -> bool:
        return len(self.queue1) == 0

Sorting Algorithms || Python || Data Structures and Algorithms

Rishab Trivedi — Tue, 17 Dec 2024 03:24:28 +0000

Sorting Algoritms

1. Bubble Sort

In this, we swap the higher element with its neighbor until we reach the end of the array. Now the highest element is at the last position. So, we change the boundary and decrease it by 1 from the last. At worst, we have to iterate n times to sort the array.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Algorithm -

Iterate over the array and find the maximum element, then swap it to the last.
Compare all adjacent elements and swap if the larger element is before the smaller element. Keep doing this until you reach the end of the array.
Maintain a flag: if no element is swapped, then we can break the loop, as the array is sorted.

Time Complexity :

Best Case - If the array is already sorted then only one iteration is required. Time complexity - O(n)
Average Case - if the array is randomly sorted, then time complexity - O(n2)
Worst Case - if the array is in decreasing order then we will require n*2 iterations.

Space Complexity - O(1), No extra memory required.

Advantages -

No extra memory required.
Stable as elements keep their relative order.

Disadvantages -

Time complexity - O(n2), which is very high for large datasets.

Applications-

Can be used only when the dataset is very small, and simplicity outweighs inefficiency due to high time complexity.

2. Selection Sort

In this, we find the smallest element in the array and replace it with the first element. Then, we increase the boundary by 1 and repeat the same steps until we reach the end of the array.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Algorithm -

Iterate over the array and find the minimum element.
Swap it with the first element and increase the pointer by 1.
Repeat this process until we reach the end of the array.

Time Complexity : It has a time complexity of O(n2) in all three cases: best, average, and worst. This is because we have to select the minimum element and swap it every time, regardless of whether the array is already sorted or not.

Space Complexity - O(1), No extra memory required.

Advantages -

No extra memory required.
Fewer swaps are done than in bubble sort.

Disadvantages -

Time complexity - O(n2), which is very high for large datasets.
Not Stable, as it does not maintain the relative order of equal elements.

Applications -

It can be used in systems with limited memory as it does not require additional storage.
It is used in systems where minimizing the number of swaps is critical, such as in systems with slow write operations.

3. Insertion Sort

It is an algorithm that works by inserting an unsorted element into its correct position by iteratively checking backwards from the position of the element to the start of the array.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Algorithm -

Start from the second element of the array and compare it with the first element. If the current element is smaller than the first element, then swap them.
Now increase the pointer and do this for the third element: compare it with the second and first elements.
Repeat the same process for the rest of the elements, comparing them with all the previous elements, and insert them at the suitable position.

Time Complexity :

- Best Case - If the array is already sorted then only one iteration is required. Time complexity is O(n)
- Average Case - if the array is randomly sorted, then time complexity is O(n2)
- Worst Case - if the array is in decreasing order then we will require n2 iterations.

Space Complexity - O(1), No extra memory required.

Advantages -

No extra memory required.
Stable, as elements keep their relative order.

Disadvantages -

Time complexity - O(n2), which is very high for large datasets.
Not Stable, as it does not maintain the relative order of equal elements.

Applications-

It is efficient for scenarios where elements arrive in real-time and need to be sorted, such as live data streams.

4. Merge Sort

Merge Sort is an algorithm that follows the divide and conquer approach. It has two main steps: first, dividing the array recursively, and second, merging the divided arrays in sorted order.

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        # Recursively split and sort the halves
        mergeSort(lefthalf)
        mergeSort(righthalf)

        # Merge the sorted halves
        merge(alist, lefthalf, righthalf)

def merge(alist, lefthalf, righthalf):
    i = j = k = 0

    while i < len(lefthalf) and j < len(righthalf):
        if lefthalf[i] < righthalf[j]:
            alist[k] = lefthalf[i]
            i += 1
        else:
            alist[k] = righthalf[j]
            j += 1
        k += 1

    while i < len(lefthalf):
        alist[k] = lefthalf[i]
        i += 1
        k += 1

    while j < len(righthalf):
        alist[k] = righthalf[j]
        j += 1
        k += 1

Algorithm -

Divide the array into two halves by calculating the mid-point.
Continue dividing until the length of each sub-array is 1.
Call the merge function on both halves: the left half and the right half.
Use three pointers for the merging process:

The first pointer for the left half array.
The second pointer for the right half array.
The third pointer for the sorted array.

Iterate through both halves and compare their elements. Insert the smaller element into the sorted array and increment the corresponding pointer by 1.
Repeat this process recursively until the entire array is sorted.

Time Complexity : Merge Sort has a time complexity of O(n log n) in all three cases: best, average, and worst. This is because, irrespective of whether the array is already sorted or not, the same steps are followed for each division and merge.

O( log n ) - The array size is halved at each step during the divide phase.

O(n) - During merging process we have to iterate over all the elements once.

So the total time complexity is O (n) * O (log n) = O (n log n)

Space Complexity - O(n), Extra memory is required during the merging process to store the temporary arrays.

Advantages -

Stable, as elements keep their relative order.
Time complexity is O (n log n), even for the large datasets.
Suitable for parallel processing because sub-arrays are merged independently.

Disadvantages -

Time complexity - O(n2), which is very high for large datasets.
Extra memory is required for the merging process.
Not in place as extra memory is required.
Slower than QuickSort in general for most datasets.

Applications -

It is used in situations where data is too large to fit in memory, such as merging large files.
It is used to sort linked lists because random access is not required.

5. Quick Sort

Quick Sort is an algorithm that follows the divide-and-conquer approach. We choose a pivot element and partition the array around the pivot element after placing the pivot in its correct sorted position.

The first step is to choose the pivot element and then partition the array around the pivot. All elements smaller than the pivot will be on the left, and all elements greater than the pivot will be on its right. The pivot is then in its correct sorted position. Recursively, the same process is applied by dividing the array into two halves: the first half contains the elements before the pivot, and the second half contains the elements after the pivot. This process is repeated until the length of each sub-array reaches 1.

def partition(arr, low, high):

    # Choosing Last Element as Pivot
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    print(arr)
    print("Pivot is ", arr[high])
    return i + 1

    # Choosing First Element as Pivot

    # pivot = arr[low]
    # i = low
    # for j in range(low, high+1):
    #     if arr[j] < pivot:
    #         i += 1
    #         arr[i], arr[j] = arr[j], arr[i]
    # arr[i], arr[low] = arr[low], arr[i]
    # print(arr)
    # print("Pivot is ", arr[high])
    # return i 



def quicksort(arr, low, high):

    if low < high:
        pi = partition(arr, low, high)

        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

Algorithm -

Divide the array into two halves by calculating the mid-point.
Choose a pivot; any element can be chosen as the pivot.
Iterate over the array and compare each element with the pivot.
Place all elements smaller than the pivot on the left and all elements greater than the pivot on the right.
Swap the pivot with the left pointer so that the pivot is at its correct sorted position.
Repeat this process recursively until the length of the partition is greater than 1.

Time Complexity :

1. Best Case - Time complexity - O(n log n), when the pivot divides the array into two equal halves.
2. Average Case - Time complexity - O(n log n), when the pivot divides the array into two equal halves. But not necessarily equal.
3. Worst case - Time complexity - O(n2) , When -

The smallest element is chosen as the pivot in an already sorted array.
The largest element is chosen as the pivot in an array sorted in decreasing order.

O( log n ) - The array size is halved at each step during the divide phase.

O(n) - During the ordering of elements.

So, the total time complexity is O (n) * O (log n) = O (n log n)

Space Complexity :

Best and Average case - O( log n) - for the recursive stack.
Worst Case - O(n) - for the recursive stack.

Advantages -

Efficient for large datasets unless the pivot is chosen bad.
It is cache friendly as we work on the same array to sort and do not copy data to to any auxiliary array.
One of the fastest general purpose algorithms for large data when stability is not required.

Disadvantages -

Time complexity - O(n2), which is very high for large datasets.
Not Stable, as it does not maintain the relative order of equal elements.

Applications -

It is used in programming libraries and frameworks. For example - Python’s sorted() function and Java’s Array.sort() is based on quick sort.
It is used indDatabase query optimization by efficiently sorting rows during query execution.
It works well for in-memory sorting of large datasets due to its cache-friendly properties.

6.Heap Sort

Heap Sort is a comparison-based sorting algorithm. It is an extension of Selection Sort. In Heap Sort, we create a Binary Heap and swap the maximum or minimum element with the last element. Then, we reduce the heap size by 1. This process is repeated until the length of the heap is greater than 1.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:

        def heapify(nums,n,i):
            largest = i
            left = 2*i +1
            right = 2*i + 2

            if left < n and nums[left] > nums[largest]:
                # nums[left],nums[largest] = nums[largest],nums[left]
                largest = left

            if right < n and nums[right] > nums[largest]:
                # nums[right] , nums[largest] = nums[largest],nums[right]
                largest = right

            if largest != i:
                nums[i],nums[largest] = nums[largest],nums[i]
                heapify(nums,n,largest)


        n = len(nums)

        # Build Max Heap
        for i in range((n//2)-1,-1,-1):
            heapify(nums,n,i)

        for i in range(n-1,0,-1):
            nums[0],nums[i] = nums[i],nums[0]
            heapify(nums,i,0)

        return nums

Algorithm -

Build a max heap using the heapify process. Heapify is a method used to maintain the heap property of a binary heap data structure.
If the array is of size n, it contains n//2 parent nodes.
For a parent at index i:

a.Its left child is at index 2i+1

b. Its right child is at index 2i+2

Iterate over all subtrees with parents from index n//2 to 0 and call the heapify function on them.
Now, the array becomes a max heap, with the largest element at index 0.
Swap the first element with the last element of the heap and decrease the size of the heap by 1.
Repeat this process until the length of the heap is greater than 1

Time Complexity : Heap Sort has a time complexity of O(n log n) in all three cases: best, average, and worst. This is because, irrespective of whether the array is already sorted or not, the same steps are followed each time a max heap is created and an element is swapped.

O( log n ) - To create max heap

O(n) - As the max heap is created and an element is swapped n times.

So the total time complexity is O (n) * O (log n) = O (n log n)

Space Complexity : For all cases - O( log n) - for the recursive stack.

Advantages -

Time complexity is O (n log n), even for the large datasets.
Memory usage is almost constant.

Disadvantages -

Not Stable, as it does not maintain the relative order of equal elements.
Many swaps are required as compared to merge sort.

Applications -

It is useful for implementing priority queues where extraction of the maximum or minimum element is frequent.
Useful in systems where in-place sorting is necessary and memory usage is critical.
It is used in scenarios where rankings are needed.

7.Counting Sort and Radix Sort

Counting Sort is a non-comparison-based sorting algorithm. It is particularly efficient when the range of input values is small compared to the number of elements to be sorted. The basic idea behind Counting Sort is to count the frequency of each distinct element in the input array and use that information to place the elements in their correct sorted positions.

Radix Sort uses Counting Sort as a subroutine. It applies Counting Sort to each digit place of a number and repeatedly sorts until it processes all the digits of the largest number in the array.

def countingSort(arr, place):
    indexarr = [0] * 10
    sortedArr = [0] * len(arr)

    for i in range(len(arr)):
        index = (arr[i] // place) % 10
        indexarr[index] += 1

    for i in range(1, len(indexarr)):
        indexarr[i] += indexarr[i - 1]

    i = len(arr) - 1
    while i >= 0:
        index = (arr[i] // place) % 10
        sortedArr[indexarr[index] - 1] = arr[i]
        indexarr[index] -= 1
        i -= 1

    for i in range(len(arr)):
        arr[i] = sortedArr[i]

def radixSort(arr):
    maxElement = max(arr)
    place = 1

    while maxElement // place > 0:
        countingSort(arr, place)
        place *= 10

    return arr

# Separate negative and non-negative numbers
        negative_nums = [num for num in nums if num < 0]
        positive_nums = [num for num in nums if num >= 0]

        # Sort negative numbers by converting them to positive
        negative_nums = [-num for num in negative_nums]
        if negative_nums:
            max_negative = max(negative_nums)
            place = 1
            while max_negative // place > 0:
                countingSort(negative_nums, place)
                place *= 10
        negative_nums = [-num for num in reversed(negative_nums)]

        # Sort positive numbers normally
        if positive_nums:
            max_positive = max(positive_nums)
            place = 1
            while max_positive // place > 0:
                countingSort(positive_nums, place)
                place *= 10

        # Combine the sorted negative and positive numbers
        return negative_nums + positive_nums

Algorithm -

Find the maximum number in the array and determine the number of digits (d) in it. If the length of the number is d, Counting Sort is called d times on the array.
Call Counting Sort for each digit place in the array, starting from the ones place, then tens place, and so on.
In Counting sort:

First, create an index array and map the elements based on their values.For example, if a digit is 4, increment the value at the 4th index of the index array.
Create a prefix sum array from the index array.
Using the prefix sum array, create a new sorted array equal to the length of the input array
For example, if the prefix sum array has a value of 2 at index 1, place the value 1 at position 2 in the sorted array and decrement the value in the prefix sum array by 1

Time Complexity :

Counting Sort has a time complexity of O(n + k), where n is the number of elements to sort and k is the range of values (size of the index array).This complexity is valid for all three cases: best, average, and worst.

This is because, irrespective of whether the array is already sorted or not, the same steps are followed each time.

Radix Sort’s time complexity increases by a factor of d, where d is the number of digits in the largest number in the array. Time complexity is O (d * (n + k))

So the total time complexity is O (d) * O(n + k) = O (d * (n + k))

Space Complexity : For all cases - O(n + k), where n is the length of the input array and k is the range of values in the index array.

Advantages -

Stable as elements keep their relative order.
Counting sort generally performs faster than all comparison-based sorting algorithms, such as merge sort and quicksort, if the range of input is of the order of the number of input.

Disadvantages -

Counting sort doesn’t work on decimal values.
Counting sort is inefficient if the range of values to be sorted is very large.
Not in place sorting algorithm, as it uses extra space O(O(n + m)).

Applications -

It is used in applications like counting character occurrences in strings.
Useful for sorting integers with a large range of values, such as IDs or phone numbers.
Efficient for sorting data with multiple keys, like dates or tuples.

[Boost]

Rishab Trivedi — Thu, 12 Dec 2024 05:13:38 +0000

Binary Search || Python || Data Structures and Algorithms

Rishab Trivedi ・ Dec 12 '24

#python #datastructures #algorithms #leetcode

Binary Search || Python || Data Structures and Algorithms

Rishab Trivedi — Thu, 12 Dec 2024 04:51:38 +0000

Binary Search

Binary Search is an algorithm that repeatedly divides the search space in half. This searching technique follows the divide and conquer strategy. The search space always reduces to half in every iteration.resulting in a time complexity of O(log(n)), where n is the number of elements.

Condition: Array should be sorted but they can also be applied on monotonic functions where we need to find the monotonically increasing or decreasing.

It works when we need to narrow down the search space in logarithmic time.

We use two pointers, left and right. Take the average of left and right to find the mid element.

Now, we check where we should move our left and right pointers based on the condition.

Mainly, three steps are required to solve a problem:

Pre-processing: Sort the input if it is not sorted.
Binary Search: Use two pointers and find the mid to divide the search space, then choose the correct half accordingly.
Post-processing: Determine the output.

Advantages of Binary Search Algorithm - Binary search is faster than linear search for large data because it cuts the array in half each time, instead of checking each element one by one. This makes it quicker and more efficient.

Limitations: Binary search only works on sorted arrays, so it's not efficient for small unsorted arrays because sorting takes extra time. It also doesn't work as well as linear search for small, in-memory searches.

Applications: It is used to search element in a sorted array with O(log(n)) time complexity and it can also be used to find the smallest or largest element in the array.

Basic Binary Search Code -

Code

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

33. Search in Rotated Sorted Array
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:
Input: nums = [1], target = 0
Output: -1

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while left <= right:

            mid = (left + right)//2
            print(f'left is {left},right is {right} and mid is {mid}')
            if nums[mid]==target:
                return mid

            if nums[mid] >= nums[left]:
                # if nums[mid]< target and target >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid +1
            else:
                # if nums[mid] < target and target <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid +1
                else:
                    right = mid - 1

        return -1

Use two pointers, left and right, and iterate until they overlap.
Find the mid element.
Since the array is sorted but rotated, we can’t simply compare the left or right elements with the mid.
First, determine which part left or right is sorted by comparing the mid pointer with the left or right pointer.
Based on this conclusion, adjust the pointers accordingly.

Time Complexity - O(log(n)) as the search space is getting divided into half in each iteration.
Space Complexity - O(1)

Monotonically Increasing

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.

Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Code

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) -1
        while left <= right:
            mid = (left+right)//2

            if mid >0 and nums[mid] < nums[mid-1]:
                right = mid -1
            elif mid < len(nums)-1 and  nums[mid] < nums[mid+1]:
                left = mid+1
            else:
                return mid

In this type of problem, we need to check for the peak by comparing the left or right element of the mid.
This helps determine whether the graph is trending upward or downward.
To find the maximum, search the upward slope and explore the right subspace.
To find the minimum, search the left subspace

Time Complexity - O(log(n)) as the search space is getting divided into half in each iteration.
Space Complexity - O(1)