Practice Problems

Platform: LeetCode  •  Topic: Arrays  •  Difficulty: Easy  •  Phase: Foundation

Solution — Hash Map (Complement Lookup)

Iterate through the array while maintaining a hash map of seen elements to their indices. For each number x, check if (target - x) exists in the hash map. If found, return both indices immediately.

Mathematical Insight

The complement of an element x for a fixed target t is uniquely t - x. Storing every seen value's index in a hash map turns the question "has t - x appeared before?" into an O(1) amortized lookup. Correctness: at step i, every index j < i is already in the map, so if a valid pair (j, i) with nums[j] + nums[i] = t exists, then nums[j] = t - nums[i] is present and is returned. A single left-to-right pass suffices because any pair (j, i) with j < i is necessarily discovered when the loop reaches i.

Complexity

• Time: O(N)
• Space: O(N)

Code

def twoSum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

Platform: Codeforces  •  Topic: Arrays  •  Difficulty: Easy  •  Phase: Foundation

Solution — Parity & Boundary Check

A watermelon weight w can be split into two positive even integers if and only if w is even and greater than 2 (since 2 can only split into 1 + 1, which are odd).

Mathematical Insight

Let w = a + b with a, b positive even integers. Then a = 2p, b = 2q with p, q >= 1, so w = 2(p + q) where p + q >= 2. Hence a valid split requires w even and w >= 4. Conversely, if w is even and w >= 4, take a = 2, b = w - 2 >= 2 — both positive and even. Therefore the answer is YES ⟺ w is even and w > 2. The edge case w = 2 fails (its only split 1 + 1 is odd), and any odd w fails because the sum of two even numbers is always even.

Complexity

• Time: O(1)
• Space: O(1)

Code

w = int(input())
if w > 2 and w % 2 == 0:
    print('YES')
else:
    print('NO')

Platform: LeetCode  •  Topic: Arrays  •  Difficulty: Easy  •  Phase: Foundation

Solution — Single Pass (Min Price Tracker)

Traverse array while updating min_price seen so far. At each step, calculate potential profit (price - min_price) and update max_profit.

Mathematical Insight

We maximize p_j - p_i over i < j, which equals max_j ( p_j - min_{i <= j} p_i ). Define the running prefix minimum m_j = min_{i <= j} p_i. Then the answer is max_j ( p_j - m_j ). Buying at the smallest price seen before selling day j is optimal because subtracting the minimum possible cost maximizes each candidate profit. Both m_j and the running best profit update in O(1), so one pass computes the global maximum.

Complexity

• Time: O(N)
• Space: O(1)

Code

def maxProfit(prices):
    min_p, max_p = float('inf'), 0
    for p in prices:
        min_p = min(min_p, p)
        max_p = max(max_p, p - min_p)
    return max_p

Platform: LeetCode  •  Topic: Strings  •  Difficulty: Easy  •  Phase: Foundation

Solution — Character Frequency Counter

Check if length of s and t are equal. Count frequencies of each character using a fixed size array of 26 integers or a hash map. Compare character counts.

Mathematical Insight

Two strings are anagrams ⟺ they have identical character multisets ⟺ their count vectors over the alphabet Σ are equal (vectors in Z^|Σ|). Equality of counts is both necessary and sufficient. The code keeps a single signed difference counter (+1 for s, -1 for t); the strings are anagrams ⟺ every difference is zero. The length check len(s) == len(t) is necessary since total character counts must agree.

Complexity

• Time: O(N)
• Space: O(1)

Code

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t): return False
    counts = {}
    for c1, c2 in zip(s, t):
        counts[c1] = counts.get(c1, 0) + 1
        counts[c2] = counts.get(c2, 0) - 1
    return all(v == 0 for v in counts.values())

Platform: Codeforces  •  Topic: Strings  •  Difficulty: Easy  •  Phase: Foundation

Solution — String Formatting & Length Condition

If string length > 10, replace middle characters with count (len - 2): s[0] + str(len(s)-2) + s[-1]. Otherwise leave unchanged.

Mathematical Insight

Mostly formatting, but the arithmetic is exact: for a word of length n > 10, the abbreviation is s[0] + str(n-2) + s[-1], where n - 2 is precisely the number of interior letters that get compressed (first and last are kept). Its printed length is 1 + digits(n-2) + 1. Each word is handled in O(1) time proportional to its (bounded) length.

Complexity

• Time: O(1) per word
• Space: O(1)

Code

n = int(input())
for _ in range(n):
    s = input()
    if len(s) > 10:
        print(f'{s[0]}{len(s)-2}{s[-1]}')
    else:
        print(s)

Platform: Codeforces  •  Topic: Strings  •  Difficulty: Easy  •  Phase: Foundation

Solution — String Filtering & Modification

Convert string to lowercase. Filter out all vowels ('a', 'o', 'y', 'e', 'u', 'i'). For each remaining consonant, insert '.' before it.

Mathematical Insight

This is pure set-membership filtering: a character survives ⟺ it is not in the vowel set {a, o, y, e, u, i}. Set lookup is O(1), so the whole transform is O(N). The output length is at most 2N because each surviving consonant contributes two characters ('.' + letter).

Complexity

• Time: O(N)
• Space: O(N)

Code

s = input().lower()
vowels = set('aoyeui')
res = []
for char in s:
    if char not in vowels:
        res.append('.' + char)
print(''.join(res))

Platform: LeetCode  •  Topic: Hashing  •  Difficulty: Easy  •  Phase: Foundation

Solution — Hash Set Lookup

Insert elements into a Hash Set while iterating. If an element already exists in the set, return True. Alternatively, check if len(set(nums)) < len(nums).

Mathematical Insight

By a cardinality (pigeonhole) argument, the array contains a duplicate ⟺ |set(nums)| < |nums|. Deduplication into a set preserves cardinality exactly when all elements are distinct; any repeated value strictly lowers the set's size. Equivalently: mapping n items into fewer than n distinct values forces at least one collision.

Complexity

• Time: O(N)
• Space: O(N)

Code

def containsDuplicate(nums):
    return len(set(nums)) < len(nums)

Platform: LeetCode  •  Topic: Two Pointers  •  Difficulty: Easy  •  Phase: Foundation

Solution — Two Pointers (Inward Convergence)

Place two pointers at start (left) and end (right). Skip non-alphanumeric characters. Compare lowercased characters at both pointers until they meet.

Mathematical Insight

After filtering to alphanumerics and lowercasing, a string t of length n is a palindrome ⟺ t[i] = t[n-1-i] for all i < n/2. The two pointers converge from both ends and check exactly these floor(n/2) symmetric pairs; skipping non-alphanumeric characters defines the filtered index sequence implicitly, so no extra string is built (O(1) space).

Complexity

• Time: O(N)
• Space: O(1)

Code

def isPalindrome(s: str) -> bool:
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum(): l += 1
        while l < r and not s[r].isalnum(): r -= 1
        if s[l].lower() != s[r].lower(): return False
        l, r = l + 1, r - 1
    return True

Platform: LeetCode  •  Topic: Sliding Window  •  Difficulty: Easy  •  Phase: Foundation

Solution — Fixed Sliding Window

Compute sum of initial window of size k. Slide window right by adding new element nums[i] and subtracting left element nums[i-k]. Track max sum / k.

Mathematical Insight

For a fixed window size k, the average is sum / k, and since 1/k is a positive constant, maximizing the average is equivalent to maximizing the window sum. Consecutive window sums satisfy the recurrence S_i = S_{i-1} + a[i] - a[i-k], each transition O(1). The answer is max_i S_i / k.

Complexity

• Time: O(N)
• Space: O(1)

Code

def findMaxAverage(nums, k):
    curr_sum = sum(nums[:k])
    max_sum = curr_sum
    for i in range(k, len(nums)):
        curr_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, curr_sum)
    return max_sum / k

Platform: LeetCode  •  Topic: Binary Search  •  Difficulty: Easy  •  Phase: Foundation

Solution — Divide & Conquer (Iterative)

Maintain left and right boundaries. Compute mid = left + (right - left) // 2. Adjust boundaries based on comparison with target until found or left > right.

Mathematical Insight

On a sorted array the predicate nums[mid] < target is monotone, which is exactly what binary search requires. Each step halves the live interval [l, r], so after t steps its size is about n / 2^t; it collapses to a single element when t = ceil(log2 n), giving O(log N). Loop invariant: if target is present, it always lies within [l, r]. Computing mid = l + (r - l) // 2 avoids integer overflow.

Complexity

• Time: O(log N)
• Space: O(1)

Code

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target: return mid
        elif nums[mid] < target: l = mid + 1
        else: r = mid - 1
    return -1

Platform: LeetCode  •  Topic: Stack  •  Difficulty: Easy  •  Phase: Foundation

Solution — Stack Matching

Push opening brackets onto stack. When encountering closing bracket, verify stack is non-empty and top element matches corresponding pair. Return len(stack) == 0.

Mathematical Insight

Valid bracket strings form a Dyck language, recognized by a pushdown automaton — a stack. A sequence is balanced ⟺ scanning left to right, every closing bracket matches the most recent unmatched opener (LIFO) and the stack is empty at the end. The stack precisely encodes the currently unmatched prefix, so a single O(N) pass decides membership.

Complexity

• Time: O(N)
• Space: O(N)

Code

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top: return False
        else: stack.append(char)
    return not stack

Platform: LeetCode  •  Topic: Queue / Deque  •  Difficulty: Easy  •  Phase: Foundation

Solution — Single Queue Rotation

Use standard queue. On push, enqueue item, then rotate queue by popping and re-pushing (size - 1) items so newest element stays at front.

Mathematical Insight

After each push of x, rotating the older n - 1 elements (dequeue then enqueue) moves them behind x, so the queue's front is always the most recently pushed element — FIFO front now behaves as LIFO top. Push costs n - 1 rotations ⟹ O(N); pop/top are O(1). For n pushes the total rotation work is Θ(n²) in the worst case, but each removal is O(1).

Complexity

• Push: O(N)
• Pop: O(1)
• Space: O(N)

Code

from collections import deque
class MyStack:
    def __init__(self):
        self.q = deque()
    def push(self, x: int):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
    def pop(self) -> int: return self.q.popleft()
    def top(self) -> int: return self.q[0]
    def empty(self) -> bool: return not self.q

Platform: LeetCode  •  Topic: Linked List  •  Difficulty: Easy  •  Phase: Foundation

Solution — Iterative Pointer Reversal

Maintain prev=None and curr=head pointers. Store next_node = curr.next, redirect curr.next = prev, advance prev = curr and curr = next_node.

Mathematical Insight

Reversal is an involution on the linked structure (applying it twice restores the original). The loop maintains the invariant "prev heads the already-reversed prefix; curr heads the untouched suffix." Each of the n next pointers is redirected exactly once, so the work is O(N) with O(1) extra space (fully in place).

Complexity

• Time: O(N)
• Space: O(1)

Code

def reverseList(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Platform: LeetCode  •  Topic: Linked List  •  Difficulty: Easy  •  Phase: Foundation

Solution — Floyd's Fast & Slow Pointers

Move slow pointer by 1 step and fast pointer by 2 steps. If fast meets slow, a cycle exists. If fast reaches None, no cycle exists.

Mathematical Insight

Suppose a cycle of length λ begins at index μ. At step t, slow is at position t and fast at 2t. They coincide once both are inside the cycle and 2t ≡ t (mod λ), i.e. t ≡ 0 (mod λ) with t >= μ. The smallest such t is <= μ + λ <= n, so they meet within O(N). Because fast gains exactly one node per step on slow, it can never leap over it — meeting is guaranteed if a cycle exists; otherwise fast reaches the end.

Complexity

• Time: O(N)
• Space: O(1)

Code

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast: return True
    return False

Platform: LeetCode  •  Topic: Linked List  •  Difficulty: Easy  •  Phase: Foundation

Solution — Dummy Head Two Pointers

Use dummy node as starting anchor. Compare current nodes of both lists, attach smaller node to tail, and advance pointer. Append remaining nodes.

Mathematical Insight

This is the merge step of merge sort. At each moment the global minimum among all remaining elements is min(head1, head2), since each list is individually sorted. Repeatedly attaching that minimum preserves sorted output order. The number of comparisons is at most n + m - 1, so the merge runs in O(N + M), and reusing the existing nodes keeps it O(1) extra space.

Complexity

• Time: O(N + M)
• Space: O(1)

Code

def mergeTwoLists(l1, l2):
    dummy = tail = ListNode(0)
    while l1 and l2:
        if l1.val < l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

Platform: LeetCode  •  Topic: Arrays  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Kadane's Algorithm

Track curr_sum = max(num, curr_sum + num) at each position. Update global max_sum = max(max_sum, curr_sum). Discards negative sub-totals.

Mathematical Insight

Kadane's method is a one-dimensional DP. Let f(i) be the maximum subarray sum ending at index i. The recurrence is f(i) = max(a[i], f(i-1) + a[i]) — either start a fresh subarray at i or extend the best one ending at i-1. The answer is max_i f(i). This is correct by optimal substructure: an optimal subarray ending at i is either a[i] alone or an optimal subarray ending at i-1 extended by a[i]. O(N).

Complexity

• Time: O(N)
• Space: O(1)

Code

def maxSubArray(nums):
    max_sum = curr_sum = nums[0]
    for num in nums[1:]:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(max_sum, curr_sum)
    return max_sum

Platform: LeetCode  •  Topic: Arrays  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Two-Pointer Permutation Pivot

1. Find rightmost index i where nums[i] < nums[i+1]. 2) Find rightmost index j > i where nums[j] > nums[i]. 3) Swap nums[i] & nums[j]. 4) Reverse suffix from i+1.

Mathematical Insight

Permutations are ordered lexicographically. The immediate successor is found by: (1) locate the longest non-increasing suffix — it is already the largest arrangement of those elements; (2) the pivot is the element just left of that suffix; (3) swap the pivot with the smallest suffix element strictly greater than it (take the rightmost such to keep the suffix sorted descending); (4) reverse the suffix, turning it from descending into ascending — the smallest possible tail. If no pivot exists the array is the final permutation, so reversing yields the first. O(N).

Complexity

• Time: O(N)
• Space: O(1)

Code

def nextPermutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i+1]: i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]: j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i+1:] = reversed(nums[i+1:])

Platform: LeetCode  •  Topic: Arrays  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Prefix Sum + Hash Map

Maintain running prefix_sum. Subarray sum equal to k implies prefix_sum - k was seen previously. Increment count by frequency of (prefix_sum - k) in hash map.

Mathematical Insight

Define prefix sums P_0 = 0 and P_j = a[0] + ... + a[j-1]. Any subarray sum equals P_j - P_i for i < j. We seek pairs with P_j - P_i = k, i.e. P_i = P_j - k. Iterating j and counting how many earlier prefixes equal P_j - k (via a frequency hash map) tallies every qualifying subarray in O(N). Seeding the map with {0: 1} accounts for subarrays that start at index 0.

Complexity

• Time: O(N)
• Space: O(N)

Code

def subarraySum(nums, k):
    counts = {0: 1}
    prefix = res = 0
    for x in nums:
        prefix += x
        res += counts.get(prefix - k, 0)
        counts[prefix] = counts.get(prefix, 0) + 1
    return res

Platform: LeetCode  •  Topic: Strings  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Hash Map with Frequency Key / Sorted Key

Map character count tuple (26 elements) to list of strings. Anagrams generate identical character count tuples.

Mathematical Insight

Define the equivalence relation s ~ t ⟺ same character multiset; anagram groups are its equivalence classes. A canonical key — the 26-length count tuple (or the sorted string) — satisfies: two strings share a key ⟺ they are anagrams. Bucketing by key therefore partitions the input into exactly the anagram groups. Building all keys costs N strings × K length ⟹ O(N·K).

Complexity

• Time: O(N * K)
• Space: O(N * K)

Code

from collections import defaultdict
def groupAnagrams(strs):
    ans = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s: count[ord(c) - ord('a')] += 1
        ans[tuple(count)].append(s)
    return list(ans.values())

Platform: LeetCode  •  Topic: Strings  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Expand Around Center

Consider each index (and pair of adjacent indices) as center of palindrome. Expand outwards while left and right characters match.

Mathematical Insight

Every palindromic substring has a center: either a single index (odd length) or the gap between two adjacent indices (even length) — there are 2n - 1 centers in all. A palindrome centered at c is characterized by the symmetry s[c-d] = s[c+d]. Expanding outward from each center while characters match finds the longest palindrome for that center; each expansion is at most n, so the total is O(N²).

Complexity

• Time: O(N^2)
• Space: O(1)

Code

def longestPalindrome(s: str) -> str:
    res = ''
    for i in range(len(s)):
        for l, r in [(i, i), (i, i+1)]:
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > len(res):
                    res = s[l:r+1]
                l -= 1; r += 1
    return res

Platform: Codeforces  •  Topic: Hashing  •  Difficulty: Easy-Medium  •  Phase: Core DSA

Solution — Hash Map Frequency Tracking

Maintain hash map of registered usernames to count. If name not seen, store count=1 & print 'OK'. Otherwise, print name + str(count) & increment count.

Mathematical Insight

This is a counter over a set of names. If a name has appeared c times before, the system prints name + str(c) and updates its count to c + 1; a first appearance prints OK. It is exactly a frequency map, and each of the n operations is O(1) amortized ⟹ O(N).

Complexity

• Time: O(N)
• Space: O(N)

Code

n = int(input())
db = {}
for _ in range(n):
    name = input()
    if name not in db:
        db[name] = 1
        print('OK')
    else:
        print(f'{name}{db[name]}')
        db[name] += 1

Platform: LeetCode  •  Topic: Hashing  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Hash Set Boundary Building

Convert array to Hash Set. Iterate set: only start counting sequence length if num - 1 is NOT in set (ensures O(1) start of sequence).

Mathematical Insight

In the value set, a maximal run of consecutive integers [x, x+1, ..., x+L-1] has a unique starting value x for which x - 1 is absent. The algorithm only begins counting from such starts, so the inner while loop, summed across all runs, touches each set element at most once. Combined with the outer loop's membership checks, every element is processed a constant number of times ⟹ O(N) overall, despite the nested loop.

Complexity

• Time: O(N)
• Space: O(N)

Code

def longestConsecutive(nums):
    num_set = set(nums)
    longest = 0
    for num in num_set:
        if num - 1 not in num_set:
            curr, streak = num, 1
            while curr + 1 in num_set:
                curr += 1; streak += 1
            longest = max(longest, streak)
    return longest

Platform: LeetCode  •  Topic: Two Pointers  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Sorting + Two Pointers

Sort array. Iterate i from 0 to N-1. Use two pointers left=i+1, right=N-1 to find pairs summing to -nums[i]. Skip duplicates for i, left, right.

Mathematical Insight

We want distinct triples summing to 0. Sort, then fix a = nums[i]; the remaining need is a pair (b, c) in the suffix with b + c = -a. On a sorted array, two pointers l, r exploit monotonicity: if nums[l] + nums[r] < -a the sum is too small so advance l; if too large, retract r. This finds all valid pairs for each i in O(N), giving O(N²) total. Sorting is what enables both the two-pointer sweep and O(1) duplicate skipping.

Complexity

• Time: O(N^2)
• Space: O(1)

Code

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums)-2):
        if i > 0 and nums[i] == nums[i-1]: continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: l += 1
            elif s > 0: r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
    return res

Platform: LeetCode  •  Topic: Two Pointers  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Greedy Two Pointers

Pointers at both ends l=0, r=N-1. Area = min(height[l], height[r]) * (r - l). Move pointer with smaller height inward (only way to potentially gain area).

Mathematical Insight

The area between walls l and r is (r - l) · min(h[l], h[r]). Start with the widest gap (pointers at both ends). The shorter wall caps the area, so moving the taller wall inward can only preserve or lower min while strictly reducing width — it can never improve the area. Hence we must move the shorter wall, discarding only configurations provably no better than the current one. Each step reduces the width by 1, so the sweep is O(N) and skips no optimal pair.

Complexity

• Time: O(N)
• Space: O(1)

Code

def maxArea(height):
    l, r = 0, len(height) - 1
    max_a = 0
    while l < r:
        max_a = max(max_a, min(height[l], height[r]) * (r - l))
        if height[l] < height[r]: l += 1
        else: r -= 1
    return max_a

Platform: LeetCode  •  Topic: Sliding Window  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Variable Sliding Window + Hash Map

Maintain sliding window [left..right]. Store last seen index of each character in Hash Map. If char seen inside window, update left = max(left, seen[char] + 1).

Mathematical Insight

Keep a window [l, r] containing only distinct characters. When s[r] repeats at a previous position p >= l, any window containing both copies is invalid, so the smallest valid start jumps to p + 1. The answer is max_r (r - l + 1). Each index enters and leaves the window exactly once ⟹ O(N). The window is always the longest valid substring ending at r.

Complexity

• Time: O(N)
• Space: O(min(N, M))

Code

def lengthOfLongestSubstring(s: str) -> int:
    seen = {}
    left = max_len = 0
    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

Platform: LeetCode  •  Topic: Sliding Window  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Dynamic Sliding Window Shrinking

Expand right pointer to accumulate window_sum. While window_sum >= target, update min_len = min(min_len, right - left + 1) and shrink left pointer.

Mathematical Insight

For positive elements the window sum is monotone in window length — adding an element only increases it. So for each right end r there is a shrink threshold on the left where sum >= target; contracting from the left while the sum stays >= target yields the shortest valid window ending at r. Each pointer advances at most n times ⟹ O(N). Positivity is precisely what makes the shrink step valid.

Complexity

• Time: O(N)
• Space: O(1)

Code

def minSubArrayLen(target, nums):
    l = curr_sum = 0
    min_len = float('inf')
    for r in range(len(nums)):
        curr_sum += nums[r]
        while curr_sum >= target:
            min_len = min(min_len, r - l + 1)
            curr_sum -= nums[l]
            l += 1
    return min_len if min_len != float('inf') else 0

Platform: LeetCode  •  Topic: Binary Search  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Rotated Binary Search

At mid, at least one half [left..mid] or [mid..right] is sorted. Identify sorted half, check if target lies within its bounds, and narrow range accordingly.

Mathematical Insight

A rotated sorted array is two sorted runs joined at the pivot. For any mid, at least one of [l, mid] or [mid, r] is a contiguous (non-wrapping) sorted run — detectable by comparing nums[l] <= nums[mid]. If the target's value lies within that sorted half's range, recurse there; otherwise recurse in the other half. Each step halves the interval ⟹ O(log N).

Complexity

• Time: O(log N)
• Space: O(1)

Code

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target: return mid
        if nums[l] <= nums[mid]: # Left half sorted
            if nums[l] <= target < nums[mid]: r = mid - 1
            else: l = mid + 1
        else: # Right half sorted
            if nums[mid] < target <= nums[r]: l = mid + 1
            else: r = mid - 1
    return -1

Platform: LeetCode  •  Topic: Stack  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Dual Stack / Pair Stack

Maintain main stack and min_stack. On push(val), push val to main stack and min(val, min_stack[-1]) to min_stack. Pop simultaneously.

Mathematical Insight

Maintain an auxiliary stack with the invariant min_stack[i] = min(vals[0..i]), so its top is always the current minimum. This works because the prefix minimum satisfies min(v_0..v_i) = min(v_i, min(v_0..v_{i-1})), computable in O(1) on push. Popping both stacks together preserves the invariant, so push, pop, top, and getMin are all O(1).

Complexity

• Time: O(1) for all ops
• Space: O(N)

Code

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, val: int):
        self.stack.append(val)
        m = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(m)
    def pop(self):
        self.stack.pop()
        self.min_stack.pop()
    def top(self) -> int: return self.stack[-1]
    def getMin(self) -> int: return self.min_stack[-1]

Platform: LeetCode  •  Topic: Stack  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Monotonic Decreasing Stack

Use stack to store indices of temperatures. While current temp > temp at stack top index, pop index idx and record answer res[idx] = curr_i - idx.

Mathematical Insight

The stack holds indices of a strictly decreasing temperature subsequence (days awaiting a warmer one). Each index is pushed once and popped at most once — when a hotter day resolves it — so total operations are <= 2n ⟹ O(N) (amortized analysis of a monotonic stack). Correctness: when temp[i] exceeds the temperature at the stack top, day i is the nearest warmer day for the popped index, since anything warmer in between would have popped it earlier.

Complexity

• Time: O(N)
• Space: O(N)

Code

def dailyTemperatures(temperatures):
    res = [0] * len(temperatures)
    stack = [] # stores indices
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            prev_i = stack.pop()
            res[prev_i] = i - prev_i
        stack.append(i)
    return res

Platform: LeetCode  •  Topic: Trees  •  Difficulty: Easy  •  Phase: Core DSA

Solution — Recursive Depth First Search (DFS)

Base case: if root is None, return 0. Recursively calculate 1 + max(maxDepth(root.left), maxDepth(root.right)).

Mathematical Insight

Standard tree-height recurrence: height(node) = 0 if the node is null, else 1 + max(height(left), height(right)). Each of the n nodes contributes exactly once to the computation ⟹ O(N) time, and the recursion stack depth equals the tree height H ⟹ O(H) space.

Complexity

• Time: O(N)
• Space: O(H)

Code

def maxDepth(root):
    if not root: return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

Platform: LeetCode  •  Topic: Trees  •  Difficulty: Easy  •  Phase: Core DSA

Solution — Recursive Tree Traversal

Base case: if root is None, return None. Swap root.left and root.right, then recursively invert both subtrees.

Mathematical Insight

Inverting a tree is the mirror map: swap each node's two children, recursively. It is an involution — applying it twice restores the original tree. Every one of the n nodes has its children swapped exactly once ⟹ O(N) time, with recursion depth H ⟹ O(H) space.

Complexity

• Time: O(N)
• Space: O(H)

Code

def invertTree(root):
    if not root: return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

Platform: LeetCode  •  Topic: Trees  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Breadth First Search (BFS Queue)

Use Queue initialized with root. At each step, measure level size = len(queue), process all nodes in current level, append values to level list and enqueue children.

Mathematical Insight

BFS visits nodes in non-decreasing distance from the root, so all nodes at depth d are enqueued before any at depth d + 1. Snapshotting len(queue) at the start of each iteration isolates exactly one level. Each node is enqueued and dequeued once ⟹ O(N) time; the queue holds at most the widest level W ⟹ O(W) space.

Complexity

• Time: O(N)
• Space: O(W)

Code

from collections import deque
def levelOrder(root):
    if not root: return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

Platform: LeetCode  •  Topic: Trees  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Recursive Bottom-Up Backtracking

Recursively search left and right subtrees. If current node is p or q or None, return root. If both subtrees return non-null, root is LCA. Otherwise return non-null child.

Mathematical Insight

The lowest common ancestor of p and q is the deepest node whose subtree contains both. A post-order recursion returns whether p or q was found below. A node whose left subtree reports one target and whose right subtree reports the other is the split point — the LCA. If both targets lie in a single subtree, the LCA is deeper on that side. One post-order pass ⟹ O(N).

Complexity

• Time: O(N)
• Space: O(H)

Code

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q: return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right: return root
    return left or right

Platform: LeetCode  •  Topic: BST  •  Difficulty: Easy  •  Phase: Core DSA

Solution — BST Property Traversal

Leverage BST ordering: if target < root.val move left; if target > root.val move right. Return node when target == root.val.

Mathematical Insight

The BST invariant is left subtree < node < right subtree. Comparing the target to node.val therefore eliminates an entire subtree at each step, since all of its values are on the wrong side of the ordering. The search follows one root-to-node path, so it runs in O(H); the iterative form uses O(1) space.

Complexity

• Time: O(H)
• Space: O(1) Iterative

Code

def searchBST(root, val):
    curr = root
    while curr and curr.val != val:
        curr = curr.left if val < curr.val else curr.right
    return curr

Platform: LeetCode  •  Topic: BST  •  Difficulty: Medium  •  Phase: Core DSA

Solution — Recursive Bounds Validation

Pass lower and upper bounds (min_val, max_val) to recursive helper. For node to be valid: min_val < node.val < max_val. Left child gets (min, val), right child gets (val, max).

Mathematical Insight

A binary tree is a BST ⟺ every node's value lies strictly inside an open interval (low, high) set by its ancestors: going left tightens the upper bound to the parent's value, going right tightens the lower bound. (Equivalently, its in-order traversal is strictly increasing.) Propagating and checking these bounds visits each node once ⟹ O(N).

Complexity

• Time: O(N)
• Space: O(H)

Code

def isValidBST(root):
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node: return True
        if not (low < node.val < high): return False
        return validate(node.left, low, node.val) and validate(node.right, node.val, high)
    return validate(root)

Platform: Codeforces  •  Topic: Binary Search  •  Difficulty: Medium  •  Phase: Advanced

Solution — Binary Search on Answer Range

Need n pipes using minimum splitters from 2 to k. Binary search number of splitters x. Sum of pipes from top x splitters is xk - x(x+1)/2 + 1. Find min x where total >= n.

Mathematical Insight

Begin with 1 pipe. A splitter of size i turns 1 pipe into i pipes, a net gain of i - 1. Using the x largest available splitters (sizes k, k-1, ..., k-x+1) maximizes the pipe count, which forms an arithmetic series: pipes(x) = 1 + sum_{j=0}^{x-1}(k - 1 - j) = x·k - x(x+1)/2 + 1. Since pipes(x) is strictly increasing in x, binary search for the smallest x with pipes(x) >= n. It is feasible only when n <= 1 + (k-1)·k/2 (all splitters used). O(log K).

Complexity

• Time: O(log K)
• Space: O(1)

Code

def solve(n, k):
    if n == 1: return 0
    if n > k*(k-1)//2 + 1: return -1
    l, r = 1, k - 1
    ans = k - 1
    while l <= r:
        mid = (l + r) // 2
        # pipes given by choosing mid largest splitters
        pipes = mid * k - mid * (mid + 1) // 2 + 1
        if pipes >= n:
            ans = mid
            r = mid - 1
        else:
            l = mid + 1
    return ans

Platform: LeetCode  •  Topic: Heap / Priority Queue  •  Difficulty: Medium  •  Phase: Advanced

Solution — Min-Heap of Size K / QuickSelect

Maintain Min-Heap of size K. Push elements; when size > K, pop minimum. Top of heap will be K-th largest element.

Mathematical Insight

A min-heap of size k keeps exactly the k largest elements seen so far; its root is the smallest of those, which is the k-th largest overall. Each push/pop is O(log k), over n elements ⟹ O(N log K) time and O(K) space. (QuickSelect achieves expected O(N) via the linearity of the expected partition sizes, but with worst case O(N²).)

Complexity

• Time: O(N log K)
• Space: O(K)

Code

import heapq
def findKthLargest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

Platform: LeetCode  •  Topic: Recursion / Backtracking  •  Difficulty: Medium  •  Phase: Advanced

Solution — Backtracking (Visited State)

Recursively build list path. Track visited elements. For each unvisited element, pick element, recurse, then backtrack (unpick).

Mathematical Insight

There are n! permutations of n distinct elements. The recursion constructs each one by choosing an unused element at every position: n choices, then n - 1, and so on, producing n! leaves in the decision tree. Copying each finished permutation costs O(N) ⟹ O(N · N!). The factorial is intrinsic — it is the size of the output itself.

Complexity

• Time: O(N * N!)
• Space: O(N)

Code

def permute(nums):
    res = []
    def backtrack(path, visited):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, num in enumerate(nums):
            if not visited[i]:
                visited[i] = True
                backtrack(path + [num], visited)
                visited[i] = False
    backtrack([], [False]*len(nums))
    return res

Platform: LeetCode  •  Topic: Recursion / Backtracking  •  Difficulty: Medium  •  Phase: Advanced

Solution — Backtracking Decision Tree

At each index i, decide whether to include nums[i] in subset. Recurse for index i+1. Append copy of current path to result list.

Mathematical Insight

A set of n elements has exactly 2^n subsets, since each element is independently in or out (a bijection with length-n binary strings). The backtracking tree enumerates all of them, and copying each subset costs O(N) ⟹ O(N · 2^N). The exponential factor is the size of the power set and cannot be avoided.

Complexity

• Time: O(N * 2^N)
• Space: O(N)

Code

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

Platform: LeetCode  •  Topic: Recursion / Backtracking  •  Difficulty: Medium  •  Phase: Advanced

Solution — DFS Grid Traversal with Backtracking

From each cell matching word[0], run DFS in 4 directions. Temporarily mark current cell as '#' to prevent reuse, recurse to match next char, then restore original character.

Mathematical Insight

DFS explores simple paths in the grid graph. From a start cell each of up to L steps branches into at most 3 new directions (the fourth is where you came from), so there are at most 4 · 3^{L-1} ≈ 4^L paths per start; over M · N starts this is O(M·N·4^L). Marking a visited cell '#' enforces the no-reuse (simple-path) constraint, and restoring it on backtrack keeps sibling branches independent. Recursion depth is at most L ⟹ O(L) space.

Complexity

• Time: O(M * N * 4^L)
• Space: O(L)

Code

def exist(board, word):
    R, C = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word): return True
        if r < 0 or r >= R or c < 0 or c >= C or board[r][c] != word[idx]: return False
        temp = board[r][c]
        board[r][c] = '#'
        res = any(dfs(r+dr, c+dc, idx+1) for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)])
        board[r][c] = temp
        return res
    return any(dfs(r, c, 0) for r in range(R) for c in range(C))

Platform: LeetCode  •  Topic: Graph  •  Difficulty: Medium  •  Phase: Advanced

Solution — Connected Components Search (BFS/DFS)

Iterate grid cells. When finding '1', increment island count and trigger DFS/BFS to sink all adjacent connected '1's into '0's.

Mathematical Insight

Model the grid as a graph: land cells are vertices, with edges between 4-adjacent land cells. Islands are exactly the connected components. A flood fill (DFS/BFS) launched from each not-yet-visited land cell sinks one entire component, so the number of fills equals the component count. Each cell is visited O(1) times ⟹ O(M·N).

Complexity

• Time: O(M * N)
• Space: O(M * N)

Code

def numIslands(grid):
    if not grid: return 0
    R, C = len(grid), len(grid[0])
    islands = 0
    def dfs(r, c):
        if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != '1': return
        grid[r][c] = '0'
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            dfs(r+dr, c+dc)
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1':
                islands += 1
                dfs(r, c)
    return islands

Platform: LeetCode  •  Topic: Graph  •  Difficulty: Medium  •  Phase: Advanced

Solution — Cycle Detection in Directed Graph (Kahn's BFS / DFS)

Build adjacency list & indegree array. Push nodes with 0 indegree to BFS queue. Process nodes, decrement indegree of neighbors. Return processed_count == numCourses.

Mathematical Insight

The prerequisites form a directed graph; a valid ordering exists ⟺ the graph is a DAG ⟺ it has no directed cycle. Kahn's algorithm repeatedly removes in-degree-0 nodes and can process all V nodes ⟺ the graph is acyclic — a cycle traps its nodes with in-degree permanently >= 1. Thus processed == numCourses ⟺ the courses are schedulable. Each edge decrements one in-degree exactly once ⟹ O(V + E).

Complexity

• Time: O(V + E)
• Space: O(V + E)

Code

from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
    adj = defaultdict(list)
    indegree = [0] * numCourses
    for u, v in prerequisites:
        adj[v].append(u)
        indegree[u] += 1
    q = deque([i for i in range(numCourses) if indegree[i] == 0])
    visited = 0
    while q:
        node = q.popleft()
        visited += 1
        for nxt in adj[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0: q.append(nxt)
    return visited == numCourses

Platform: Codeforces  •  Topic: Graph  •  Difficulty: Medium  •  Phase: Advanced

Solution — Greedy Reverse Traversal / Shortest Path BFS

Work backwards from m to n. If m > n: if m is odd, add 1 (m += 1); if m is even, divide by 2 (m //= 2). If m <= n, add (n - m) steps.

Mathematical Insight

Forward operations from n are ×2 (red) and -1 (blue), targeting m. Reason backward from m, where the inverse operations are ÷2 (only when even) and +1. Greedy: if m > n and even, halving is the fastest way to shrink; if m is odd, add 1 first (you cannot halve an odd number). Once m <= n, only +1 steps remain, costing exactly n - m. Halving dominates repeated subtraction, which makes this parity-driven greedy optimal, and each halving roughly bisects m ⟹ O(log M).

Complexity

• Time: O(log M)
• Space: O(1)

Code

n, m = map(int, input().split())
steps = 0
while m > n:
    if m % 2 == 1: m += 1
    else: m //= 2
    steps += 1
print(steps + (n - m))

Platform: LeetCode  •  Topic: Dynamic Programming  •  Difficulty: Medium  •  Phase: Advanced

Solution — 1D Bottom-Up Dynamic Programming

Define dp[i] = min coins needed for amount i. dp[0] = 0, all others inf. Transition: dp[i] = min(dp[i], dp[i - coin] + 1) for coin <= i.

Mathematical Insight

Let dp[a] be the minimum number of coins summing to amount a, with dp[0] = 0. The recurrence is dp[a] = min over coins c <= a of dp[a - c] + 1. Optimal substructure: an optimal solution for a uses some coin c, leaving an optimal sub-solution for a - c. Subproblems overlap heavily, so a bottom-up table is efficient: O(amount · #coins) time, O(amount) space. Coins are unbounded because dp[a - c] may itself already include copies of c.

Complexity

• Time: O(amount * N)
• Space: O(amount)

Code

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Platform: LeetCode  •  Topic: Dynamic Programming  •  Difficulty: Medium  •  Phase: Advanced

Solution — Patience Sorting / Binary Search (tails array)

Maintain tails array where tails[i] stores smallest tail of all increasing subsequences of length i+1. For each x in nums, binary search location in tails and replace/append.

Mathematical Insight

Maintain tails, where tails[i] is the smallest possible tail of any increasing subsequence of length i + 1. Two facts drive correctness: tails is strictly increasing, and for each new x, replacing the first tails[j] >= x keeps tails minimal (a better tail for length j + 1), while an x exceeding all entries extends the longest run by one. Then len(tails) equals the LIS length. The binary search per element gives O(N log N).

Complexity

• Time: O(N log N)
• Space: O(N)

Code

from bisect import bisect_left
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        idx = bisect_left(tails, x)
        if idx == len(tails): tails.append(x)
        else: tails[idx] = x
    return len(tails)

Platform: LeetCode  •  Topic: Hashing  •  Difficulty: Hard  •  Phase: Challenge

Solution — Sliding Window Helper Reduction

Exact(K) = AtMost(K) - AtMost(K - 1). Implement helper function atMost(k) using sliding window with frequency hash map to count subarrays with <= k distinct elements.

Mathematical Insight

Let atMost(k) count subarrays with at most k distinct integers. Since {exactly k} = {<= k} \ {<= k-1} and the latter is a subset of the former, the count of exactly-k subarrays is atMost(k) - atMost(k-1). And atMost(k) is computed with a sliding window: as r extends, shrink l while the window has more than k distinct values; each r then contributes (r - l + 1) valid subarrays ending at r. Two O(N) passes ⟹ O(N).

Complexity

• Time: O(N)
• Space: O(K)

Code

from collections import defaultdict
def subarraysWithKDistinct(nums, k):
    def atMost(goal):
        counts = defaultdict(int)
        l = res = 0
        for r, x in enumerate(nums):
            if counts[x] == 0: goal -= 1
            counts[x] += 1
            while goal < 0:
                counts[nums[l]] -= 1
                if counts[nums[l]] == 0: goal += 1
                l += 1
            res += (r - l + 1)
        return res
    return atMost(k) - atMost(k - 1)

Platform: LeetCode  •  Topic: Queue / Deque  •  Difficulty: Hard  •  Phase: Challenge

Solution — Monotonic Decreasing Deque

Maintain deque storing indices whose values are strictly decreasing. Pop smaller elements from back before pushing current element. Pop front element if outside window range.

Mathematical Insight

The deque stores indices whose values are strictly decreasing, so its front is always the window maximum. Two invariants maintain this: indices that fall outside [i-k+1, i] are dropped from the front, and any back element whose value is <= the incoming value is popped (it can never again be the maximum while a newer, larger, later element exists). Each index is pushed and popped once ⟹ O(N), and the deque holds at most k indices ⟹ O(K).

Complexity

• Time: O(N)
• Space: O(K)

Code

from collections import deque
def maxSlidingWindow(nums, k):
    dq = deque()
    res = []
    for i, x in enumerate(nums):
        if dq and dq[0] < i - k + 1: dq.popleft()
        while dq and nums[dq[-1]] <= x: dq.pop()
        dq.append(i)
        if i >= k - 1: res.append(nums[dq[0]])
    return res

Platform: LeetCode  •  Topic: Trees  •  Difficulty: Hard  •  Phase: Challenge

Solution — Tree Recursive DFS Global Max Tracker

DFS returns max single branch contribution max(0, gain). At node, path sum passing through node is val + left_gain + right_gain. Update global max, return val + max(left_gain, right_gain).

Mathematical Insight

Any root-to-root path bends at a unique highest node. Define gain(node) = the best sum of a downward path starting at node = node.val + max(0, max(gain(left), gain(right))), where the max(0, ...) drops negative branches. The best path bending at a node is node.val + max(0, gain(left)) + max(0, gain(right)); track the global maximum of this over all nodes, while returning only the single-branch gain upward so ancestors can extend it. One post-order pass ⟹ O(N).

Complexity

• Time: O(N)
• Space: O(H)

Code

def maxPathSum(root):
    max_sum = float('-inf')
    def dfs(node):
        nonlocal max_sum
        if not node: return 0
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))
        max_sum = max(max_sum, node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return max_sum

Platform: LeetCode  •  Topic: Heap / Priority Queue  •  Difficulty: Hard  •  Phase: Challenge

Solution — Two Balanced Heaps (Max-Heap & Min-Heap)

Maintain max_heap (small numbers) and min_heap (large numbers). Balance sizes so len(max_heap) == len(min_heap) or len(max_heap) == len(min_heap) + 1. Median is top of max_heap or avg of tops.

Mathematical Insight

Partition the streamed multiset into a lower half (a max-heap small) and an upper half (a min-heap large) satisfying all(small) <= all(large) and the size balance |small| = |large| or |small| = |large| + 1. Then the median is top(small) when the count is odd, else (top(small) + top(large)) / 2. Insertion (push, shuffle the extreme across, rebalance sizes) is O(log N); reading the median is O(1). The invariant is what keeps the two heap-tops straddling the true median.

Complexity

• Add: O(log N)
• Median: O(1)
• Space: O(N)

Code

import heapq
class MedianFinder:
    def __init__(self):
        self.small = [] # Max-heap (negated)
        self.large = [] # Min-heap
    def addNum(self, num: int):
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))
    def findMedian(self) -> float:
        if len(self.small) > len(self.large): return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2.0

Platform: Codeforces  •  Topic: Dynamic Programming  •  Difficulty: Medium-Hard  •  Phase: Challenge

Solution — Unbounded Knapsack 1D DP

Define dp[i] = max ribbon pieces to achieve length i. Base case dp[0] = 0, rest -inf. Transition: dp[i] = max(dp[i-a], dp[i-b], dp[i-c]) + 1 for valid previous states.

Mathematical Insight

This is an unbounded knapsack maximizing piece count. Let dp[i] be the maximum number of pieces summing to exactly length i, using sizes a, b, c without limit. The recurrence is dp[i] = 1 + max(dp[i-a], dp[i-b], dp[i-c]) over feasible, reachable predecessors, with dp[0] = 0 and unreachable states marked -1. The answer is dp[n]. The reachability guard (dp[i-piece] != -1) ensures only valid decompositions are counted. O(N) time and space.

Complexity

• Time: O(N)
• Space: O(N)

Code

n, a, b, c = map(int, input().split())
dp = [-1] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    for piece in (a, b, c):
        if i >= piece and dp[i - piece] != -1:
            dp[i] = max(dp[i], dp[i - piece] + 1)
print(dp[n])