DSA In Python + Top 130 Leetcode Problems for MAANG

Master time and space complexity analysis to evaluate how algorithms grow with input, measuring time by counting operations and space by RAM usage, in Big O notation.

Explore how big O notation expresses time and space complexity, illustrating linear, constant, quadratic, and logarithmic behavior.

Assess interview viability by estimating operation counts from problem constraints, applying time complexity rules (n, n log n), and recognizing hints toward binary search, backtracking, or dynamic programming.

Analyze time complexity of simple for loops by counting operations, demonstrate O(n) and O(1) cases, and explain big-O rules like ignoring constants and lower value terms.

Analyze how a doubling while loop runs in O(log n) time by counting iterations. Examine nested loops that yield O(mn) time and how to apply Big-O reasoning.

Explore myths about time complexity by comparing two loops, one running n times and the other n/2 times, but both share the same growth rate.

Learn to calculate time complexity of recursive algorithms using the recursion tree method, illustrated by a factorial example, and compare with other approaches like master theorem and back substitution.

Examine the fibonacci function's time and space complexity through a recursion tree, showing exponential time due to two recursive calls and depth n−1, with about 2^(n−1) calls.

Explore space complexity by measuring memory growth with input size, accounting for variables, external data structures, and recursion, and learn practical steps to compute it, including O(n) examples.

Learn space complexity with a simple array program that doubles elements, shows input arrays aren’t counted, avoids recursion, and yields a fixed, O(1) space.

Compute space complexity for a fibonacci recursion by examining recursion depth and the call stack, showing linear growth o(n) from storing n−1 integers.

Explore how arrays are stored contiguously in memory, enabling constant-time access and updates, while noting homogeneous types and memory location calculations that drive performance.

Explore the drawbacks of arrays, including fixed size and costly insertions or deletions in the beginning or middle caused by shifting, and how resizable arrays and linked lists address them.

Learn how resizable arrays overcome static-size limits by doubling capacity, copying elements, and using structures like ArrayList or vector to achieve amortized O(1) adds.

Learn Python lists as dynamic arrays, access by index, and use append and pop efficiently; avoid middle insertions or removals due to O(n) time, and consider alternatives.

Explore Python list operations, from iteration with for loops to concise list comprehension, and build one-dimensional, two-dimensional, and three-dimensional lists, including tuples and conditional filters for coding interviews.

Learn python list slicing, with start point, end point, and jump, producing non-inclusive sublists and defaults, while recognizing syntactic sugar that speeds coding for competitive programming.

Compute max consecutive ones in a binary array with a running count and best value, resetting on zeros; this linear O(n) approach relates to the maximum sum subarray.

Master the best time to buy and sell a stock with one transaction, using a running minimum price to maximize profit in Python.

Learn to solve the leetcode product of array except self without division using left and right product arrays in Python. Implement an O(n) time solution.

Rotate an array to the right by k in Python using an in-place method: use k mod n and three reversals—the whole array, the first k, and the last n-k.

Explore Kadane's algorithm to find the maximum subarray sum by maintaining a current sum and resetting when negative. Implement it in Python with O(n) time.

Learn to solve the maximum product subarray problem by maintaining both max and min products at each index, handling negative numbers, and implementing an efficient Python solution with O(n) time.

Learn to validate a sudoku by using nine sets for rows, columns, and grids, checking for duplicates among digits 1–9 and ignoring empty cells; grid index uses i//3 and j//3.

Explore why sorting is a fundamental technique, from major algorithms and the divide and conquer paradigm to the prerequisite of sorted input for binary search and Bellman-Ford.

Sort arrays to ascend or descend, enabling efficient algorithms like binary search and two-pointer methods. Explore core sorting algorithms—bubble, selection, insertion, merge, quicksort, heapsort, radix, and counting sort.

Describe how bubble sort sorts an array in ascending order by repeatedly swapping out-of-order adjacent elements, moving the largest element to the end and shrinking the unsorted portion.

Demonstrates a Python bubble sort implementation using nested loops to swap adjacent elements when out of order, and explains the O(n^2) time complexity.

Explore the selection sort algorithm, where the smallest element in the unsorted portion is swapped into the front in each iteration, progressively building a sorted portion of the array.

Learn to implement selection sort by finding the smallest element in the unsorted portion and swapping it to the front, using two nested loops and a n^2 time complexity.

Explain insertion sort, inserting each unsorted element into the correct position in the sorted part by shifting larger elements; best case is O(n) when already sorted.

Implement insertion sort by iterating from index 1, shifting greater elements right, and inserting the key. It runs in O(n) best case and O(n^2) worst case.

Understand how to merge two sorted arrays into a single sorted array with two pointers. Learn how the merge operation yields linear-time merging and enables practical groundwork for merge sort.

Implement a merge algorithm to combine two sorted arrays a and b into c using a while loop and indices i, j, and k; verify sorted output and O(n+m) complexity.

Explore merge sort as a divide and conquer algorithm that divides the array, sorts left and right halves recursively, then merges them into a fully sorted result.

implement a merge sort by recursively sorting the subarray between left and right indices, merging the halves, and copying back; note the time complexity o(n log n) and space o(n).

Explain how the quicksort partition function places the pivot at its correct position by dividing the array into less than, equal to, and greater than the pivot, via two-way partition.

Implement the quicksort partition with the last element as pivot, partitioning by swapping to place elements ≤ pivot on the left and > pivot on the right, illustrating O(n) complexity.

Explore the idea behind quicksort, focusing on partitioning into less-than, equal-to, and greater-than sections, placing the pivot in its correct position, and recursively sorting the subarrays.

Implement quicksort in python with a partition function and a last-element pivot, recursively sorting the left and right subarrays, and analyze best and worst case time and space complexity.

Explore counting sort, a non-comparison based algorithm that achieves linear time using a frequency array and cumulative counts. Learn its stability as a stable sort.

Learn to implement counting sort with a frequency array, compute cumulative frequencies, and place elements from right to left using a temp array, with O(n+m) time and space.

Move all zeros to the end in linear time by moving non-zero elements to the front with a start pointer and swaps, preserving their relative order.

Learn to find the majority element in an array using the Morse voting algorithm in linear time and constant space, with a Python implementation.

Learn to sort zeros, ones, and twos in place using a two-pointer partitioning method, avoiding built-in sorts to achieve linear time in the sort colors problem.

Explore the drawbacks of arrays from their contiguous memory, which enables fast access but makes middle insertions and deletions costly due to shifting. Learn how linked lists address these drawbacks.

Linked lists store data in nodes linked by references, enabling easy middle insertions and deletions. Arrays are contiguous and offer direct access, but require shifting for middle changes.

Learn how to implement a singly linked list in Python, create a node with data and next, connect nodes to form a list, and traverse to print.

Create a new node, link it to the current head, and update head to insert at the front of the linked list, including the empty-list case.

Learn to insert a node at the end of a linked list by creating the node, traversing to the last node, and updating its next pointer, with empty-list handling.

Master inserting a node in the middle of a singly linked list after a given position by traversing to i-1 and updating pointers, with edge-case handling and front insertion.

Delete nodes in a linked list from the front, some position, or the end by updating head to head.next, with head null checks and constant time at the top.

Learn to delete the last node of a linked list by traversing to the penultimate node and setting its next to null, handling empty and single-node edge cases.

Implement delete-at-end for a singly linked list by handling one-node cases with head becoming null and multi-node cases by traversing to second last node and setting its next to null.

Identify the intersection node of two linked lists by aligning their lengths and using two pointers, achieving O(m+n) time and O(1) space.

Merge two sorted linked lists by comparing values with two pointers and splicing nodes into a sorted merged list. Return the head of the merged list.

Learn to detect a linked list cycle using the hare and tortoise two-pointer method with slow and fast pointers, handling edge cases, and analyzing O(n) time.

Reverse a singly linked list using a recursive approach from the head. Return the head of the reversed list and learn base cases, node.next pointers, and O(n) time and space.

Explore how to determine a palindrome linked list in O(n) time and O(1) space by reversing the second half and comparing halves iteratively.

Detects the start of a cycle in a linked list using slow and fast pointers. If a cycle exists, a pointer from head finds the start; otherwise, returns null.

Learn to find the middle of a singly linked list in one iteration using slow and fast pointers, returning the second middle for even lengths.

Learn to add two numbers stored as reversed linked lists using digit-by-digit addition with carry. Build the resulting linked list with two pointers and implement in Python.

Remove the nth node from the end of a linked list using a one-pass two-pointer approach with a gap of n+1, handling head deletions and edge cases.

Explore hash tables, an associative data structure like a dictionary, enabling get and put operations on key–value pairs with near-constant time.

Explore how a hash table uses a pure, stateless hash function to map keys to array indices via modulo, store and retrieve values, and resolve collisions.

Explore hash table collisions and collision resolution using chaining. Learn how linked lists handle multiple keys per slot, ensuring amortized O(1) inserts and lookups, with worst case O(n).

Explore unordered and ordered hash tables, including their internal structures—array vs balanced binary search tree—and compare worst and average time complexities to guide when to use each.

Learn how to use unordered hash tables in Python with dict, add and remove keys, test presence with in, iterate keys, and obtain key lists.

Explore python's ordered dictionary using collections.OrderedDict, showing that it remembers insertion order, differs from standard dict by guaranteed output order, and when to use it for performance or order-sensitive tasks.

Solve the contains duplicate problem using a hash table or set in Python to detect any value in nums that appears at least twice.

Group all anagrams in a given string array by sorting each string to form a key and storing groups in a hash table; the final order of groups doesn't matter.

Master the two sum problem with a hash table to return indices in O(n) time and O(n) space, for unsorted arrays with exactly one solution.

Master the three sum problem by sorting the array and using the two pointer method to find unique triplets that sum to zero, reducing brute-force n^3 to n^2 time.

Explore the longest consecutive sequence in an unsorted array by using a set to start from numbers with no predecessor and count consecutive runs in linear time.

Explore the stack as an abstract data type with last in, first out behavior, covering push, top, and pop, with O(1) push/top and O(n) pop, linked lists or arrays.

Explore using stacks in Python by treating Python's built-in lists as stacks with append and pop, and access the top as the last item, while noting scalability drawbacks.

Explore using the collections module's deck class to implement a stack as a double-ended queue with push and pop on both sides, highlighting memory efficiency and simple interface.

Use a stack to determine if a string of three bracket types: round, curly, and square, is balanced, ensuring correct order and matching types, with a linear time O(n) solution.

Learn to evaluate reverse Polish (postfix) notation using a stack by processing tokens, pushing operands, and applying operators +, -, *, / to produce the final result.

Design a min stack with push, pop, top, and getmin in constant time using two stacks: a main stack for all elements and an auxiliary stack for current minimums.

Learn to solve next greater element II problem on a circular array using a stack and delayed processing to find the next greater element to the right in linear time.

Merge overlapping intervals by sorting them by start time, then end time on ties, and merge overlaps to form non-overlapping intervals; the Python solution shows O(n log n) time.

Explore the queue, a FIFO abstract data type with enqueue and dequeue operations. Compare it to a stack, and note common implementations like linked lists and built-in language support.

Learn how to implement queues with linked lists, covering standard queues, double ended queues, and priority queues, including front and back operations and the use of head and tail pointers.

Learn to use Python's collections deque as a queue by appending with append and removing from the left with pop left, illustrating FIFO and front access via q[0].

Master the sliding window approach to find the longest substring without repeating characters, using a two-pointer technique and a hash table to track character counts, with an O(n) solution.

Learn to compute the sliding window maximum in Python using a deque to maintain useful indices, discarding out-of-window elements to output the max in every window of size k.

Use the two-pointer method on a sorted, one-indexed array to find two numbers that sum to a target, returning their 1-based indices.

Analyze the trapping rainwater problem on an elevation map and compute trapped water using a two-pointer approach with left and right maximum arrays.