Reference library

Algorithms & data structures

Classic patterns — search, sort, stacks, queues, and practical complexity-aware code.

2 matches

Find the Duplicate Number in Python Using Floyd's Cycle Detection

Detects the duplicate integer in an array of n+1 numbers (values 1 to n) in O(n) time and O(1) space using Floyd's cycle detection algorithm applied to a linked-list model.

floyd-cycle duplicate-number two-pointers

Python

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[0]
    
    # Phase 1: Find intersection point of the cycle
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    # Phase 2: Find the start of the cycle (the duplicate)
    slow = nums[0…

14 0 Open

Algorithms & data structures medium

Product of All Elements Except Self in Python

Given a list of integers, return a list where each element is the product of all other elements except itself, using prefix and suffix products in O(n) time and O(1) extra space.

array prefix suffix

Python

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]
    
    right_product = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]
    
…

14 0 Open

Browse by section

Each section groups closely related Python snippets.