divide-and-conquer

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.22 Common Bugs

15.22 Common Bugs Problem Divide-and-conquer algorithms often fail in ways that are difficult to see from the high-level design. The recurrence may be correct. The idea may be standard. The code may even work for ordinary examples. Then a small input breaks it: [] [1] [2, 1] [1, 1, 1] or a boundary case causes: infinite recursion missing element duplicate element wrong pivot position stack overflow incorrect count How do...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.13 Median of Medians

15.13 Median of Medians Problem Quickselect finds the (k)-th smallest element in expected linear time. In practice, this is often sufficient. Random pivots work well, and the probability of repeatedly choosing poor pivots is low. However, some applications require stronger guarantees. Examples include: real-time systems adversarial inputs security-sensitive software theoretical algorithm analysis worst-case performance guarantees Can we design a selection algorithm that always runs in linear time, regardless of the...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.8 Fast Exponentiation

15.8 Fast Exponentiation Problem You need to compute: $$ x^n $$ where (n) is a nonnegative integer. The direct method multiplies (x) by itself (n) times: x * x * x * ... * x This takes: $$ O(n) $$ multiplications. For small exponents this is fine. For large exponents, especially in modular arithmetic, cryptography, combinatorics, and numerical code, linear exponentiation is too slow. Can divide and conquer reduce the...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.9 Divide-and-Conquer Dynamic Programming

15.9 Divide-and-Conquer Dynamic Programming Problem Many dynamic programming algorithms compute a table with the recurrence: $$ dp[i] = \min_{j < i} \left(dp[j] + cost(j,i)\right) $$ A direct implementation evaluates every possible transition. for i for j < i evaluate transition This requires: $$ O(n^2) $$ time. For (n=10^5), quadratic complexity is often too expensive. Even when the recurrence itself is simple, evaluating all possible transition points becomes the dominant cost....

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.16 Fast Fourier Transform

15.16 Fast Fourier Transform Problem You need to multiply two polynomials. Example: $$ A(x)=3+2x+5x^2 $$ $$ B(x)=1+4x $$ The product is: $$ C(x)=A(x)B(x) $$ A direct coefficient-by-coefficient multiplication compares every term of (A) with every term of (B). For two polynomials with (n) coefficients, this costs: $$ O(n^2) $$ That is acceptable for small inputs. It is too slow for large signals, big integer arithmetic, convolution, image processing, and many...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.21 Testing Divide-and-Conquer Algorithms

15.21 Testing Divide-and-Conquer Algorithms Problem Divide-and-conquer algorithms are prone to subtle implementation errors. The high-level idea may be correct, but bugs often appear in: base cases split boundaries merge logic pivot handling recursive termination index ranges temporary buffers These bugs may not appear on ordinary examples. A merge sort can pass random tests while failing on duplicates. A binary search can work for most inputs while looping forever on a...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.12 Selection Algorithms

15.12 Selection Algorithms Problem You need to find the (k)-th smallest element in an unsorted array. Examples: array = [9, 1, 6, 3, 8, 2, 7] k = 3 The 3rd smallest element is: 3 A simple solution is to sort the array and index into the sorted result. sort.Ints(nums) answer := nums[k-1] This works, but sorting does more work than necessary. Sorting gives the complete order: 1, 2, 3,...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.24 Case Studies

15.24 Case Studies Problem You have learned the mechanics of divide and conquer: split solve recursively combine But in real systems, problems rarely announce themselves as textbook recurrences. You may see a slow batch job, an expensive query engine, a data-processing task, or a geometric search problem. The challenge is recognizing which part of the work can be decomposed and which part must be combined carefully. How do divide-and-conquer techniques...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.1 Recursion Trees

15.1 Recursion Trees Problem You are given a recursive algorithm and want to determine its time complexity. The implementation repeatedly divides a problem into smaller subproblems, performs some work at each level of recursion, and eventually reaches a base case. A recurrence such as $$ T(n) = 2T\left(\frac{n}{2}\right) + n $$ describes the running time, but the growth rate is not immediately obvious. How can you visualize the work performed...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.18 Closest Pair of Points

15.18 Closest Pair of Points Problem Given (n) points in a plane, find the pair with the smallest Euclidean distance. Example: (2,3) (12,30) (40,50) (5,1) (12,10) (3,4) The closest pair is: (2,3) (3,4) with distance: $$ \sqrt{(3-2)^2+(4-3)^2} = \sqrt{2} $$ A straightforward solution compares every pair of points. point 1 vs point 2 point 1 vs point 3 ... point n-1 vs point n The number of comparisons is: $$...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.11 Cache-Oblivious Algorithms

15.11 Cache-Oblivious Algorithms Problem An algorithm can have good asymptotic complexity and still run poorly on real hardware. Modern machines do not access all memory at the same speed. Data may live in registers, L1 cache, L2 cache, L3 cache, main memory, or disk. Moving data between these levels can cost more than arithmetic. A conventional algorithm often assumes this model: memory access costs O(1) Real machines behave more like...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.23 Design Patterns

15.23 Design Patterns Problem After studying many divide-and-conquer algorithms, they can appear unrelated. Consider: Merge sort Quick sort Quickselect FFT Closest pair of points Karatsuba multiplication Strassen multiplication Binary search Inversion counting Offline query processing The details differ dramatically. Some work on arrays. Some work on geometry. Some work on algebra. Some work on answer spaces rather than data. How do experienced algorithm designers recognize when divide and conquer is...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.15 Binary Search on Answer

15.15 Binary Search on Answer Problem Some problems ask for an optimal value rather than a specific object. Examples: What is the minimum machine speed needed to finish all jobs within 8 hours? What is the smallest capacity truck that can transport all packages in 5 days? What is the largest minimum distance possible between installed routers? What is the minimum time required for a group of workers to complete...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.17 Offline Queries

15.17 Offline Queries Problem You need to answer many queries over a fixed dataset. Example: array = [5, 1, 7, 3, 9, 2] queries: count values <= 4 in range [1, 5] count values <= 6 in range [0, 3] count values <= 8 in range [2, 5] A direct approach handles each query independently. For each range, scan the relevant portion of the array. If there are (q) queries...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.19 Correctness Proofs

15.19 Correctness Proofs Problem A divide-and-conquer algorithm may look correct because its structure is simple: split solve recursively combine But many bugs hide in the boundaries: left half right half base case merge step pivot position strip condition A fast algorithm is not useful unless it computes the right result. How do we prove that a divide-and-conquer algorithm is correct? Solution Use induction on input size. Most divide-and-conquer correctness proofs...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.2 Master Theorem

15.2 Master Theorem Problem Many divide-and-conquer algorithms produce recurrences of the form $$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$ where: (a) is the number of recursive subproblems. (n/b) is the size of each subproblem. (f(n)) is the non-recursive work performed at each call. For simple recurrences, recursion trees provide an intuitive solution. For larger algorithms, repeatedly constructing trees becomes tedious. Is there a systematic way to solve an entire class of divide-and-conquer recurrences? Solution...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.10 Parallel Divide and Conquer

15.10 Parallel Divide and Conquer Problem Divide-and-conquer algorithms naturally create independent subproblems. Merge sort sorts the left half and right half independently. Quick sort partitions the array and then recursively sorts both sides. Matrix multiplication splits work into independent block products. On a single core, these recursive calls run one after another. On modern hardware, this leaves available CPU cores idle. How can we turn recursive decomposition into parallel execution...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.7 Strassen Multiplication

15.7 Strassen Multiplication Problem Karatsuba's algorithm demonstrates that multiplication can be accelerated by reducing the number of recursive subproblems. The same question naturally arises for matrix multiplication. Given two (n \times n) matrices: $$ A $$ and $$ B $$ the classical algorithm computes: $$ C = AB $$ using three nested loops. For each element: $$ C_{ij} $$ we compute: $$ C_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj} $$ The running time is: $$ O(n^3)...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.5 Closest Pair of Points

15.5 Closest Pair of Points Problem Given (n) points on a two-dimensional plane, find the pair of points whose Euclidean distance is minimal. For example: Point Coordinates A (2, 3) B (12, 30) C (40, 50) D (5, 1) E (12, 10) F (3, 4) The closest pair is: A(2,3) F(3,4) with distance: $$ \sqrt{(3-2)^2+(4-3)^2} $$ A straightforward solution compares every pair of points. With (n) points: $$ \binom{n}{2} =...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.3 Merge Sort Revisited

15.3 Merge Sort Revisited Problem You need to sort a collection of elements efficiently while preserving the relative order of equal values. The input may already be partially sorted, completely random, or adversarially arranged. Quadratic algorithms such as selection sort, insertion sort, and bubble sort become impractical as input size grows. For an array containing one million elements, an (O(n^2)) algorithm may require trillions of comparisons, while an (O(n \log...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.6 Karatsuba Multiplication

15.6 Karatsuba Multiplication Problem You need to multiply very large integers. The numbers may contain hundreds, thousands, or millions of digits. The grade-school multiplication algorithm works, but it performs one multiplication for every pair of digits. For two (n)-digit numbers, that gives: $$ O(n^2) $$ single-digit multiplications. For small numbers, this is acceptable. For large integers used in symbolic computation, cryptography, computer algebra, or arbitrary-precision arithmetic, quadratic multiplication becomes expensive....

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.14 Counting Inversions

15.14 Counting Inversions Problem You need to measure how far an array is from being sorted. Given an array: [2, 4, 1, 3, 5] an inversion is a pair of indexes: $$ i < j $$ such that: $$ a[i] > a[j] $$ In this array, the inversions are: (2, 1) (4, 1) (4, 3) So the inversion count is: 3 A sorted array has zero inversions. A reverse-sorted array...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.4 Quick Sort Revisited

15.4 Quick Sort Revisited Problem Merge sort guarantees (O(n \log n)) performance and stable ordering, but it requires additional memory proportional to the input size. For large datasets, memory allocation and copying can become significant costs. Can we design a divide-and-conquer sorting algorithm that sorts data in place while maintaining excellent practical performance? Solution Use Quick Sort. Quick sort partitions an array around a selected pivot element. After partitioning, all...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.25 Exercises

15.25 Exercises Problem You have learned the main divide-and-conquer patterns in this chapter. To make the techniques usable, you need practice turning a problem statement into: split recursive solution combine proof complexity analysis tests This section gives a set of exercises designed to reinforce the chapter. Each exercise includes the intended pattern, expected complexity, and implementation hints. Treat these as recipes to complete, not as isolated puzzles. Exercise 1: Implement...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.20 Complexity Analysis

15.20 Complexity Analysis Problem You have a divide-and-conquer algorithm and need to analyze its running time and memory usage. The code may look simple: solve(input) split input solve left solve right combine but the actual cost depends on several details: How many subproblems are created? How large are the subproblems? How expensive is the combine step? How deep is the recursion? How much auxiliary memory is allocated? Are subproblems balanced...

Programming › Algorithm Cookbook ›

Chapter 15. Divide and Conquer

Practice › Codeforces Solutions › Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2) ›

CF 2222G - Statistics on Tree

CF 2222G - Statistics on Tree Rating: - Tags: binary search, brute force, dfs and similar, divide and conquer, graphs, trees Solve time: 6m 33s Verified: no Solution Problem Understanding We are given a tree. For a pair of vertices $(u,v)$, we remove every edge belonging to the unique simple path between them. After those edges are deleted, the tree breaks into several connected components. The value of the pair...

Practice › Codeforces Solutions › Codeforces Round 274 (Div. 1) ›

CF 480E - Parking Lot

CF 480E - Parking Lot Rating: 2800 Tags: data structures, divide and conquer Solve time: 5m 24s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 939 (Div. 2) ›

CF 1956D - Nene and the Mex Operator

CF 1956D - Nene and the Mex Operator Rating: 2000 Tags: bitmasks, brute force, constructive algorithms, divide and conquer, dp, greedy, implementation, math Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a short array of length at most 18. The only allowed move is to pick a contiguous segment, compute the mex of that segment, and overwrite the entire segment with that mex value. This operation...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951E - No Palindromes

CF 1951E - No Palindromes Rating: 2000 Tags: brute force, constructive algorithms, divide and conquer, greedy, hashing, implementation, math, strings Solve time: 1m 1s Verified: no Solution Problem Understanding We are given a string and we are allowed to cut it into contiguous pieces. The goal is to decide whether we can cut it so that every resulting piece is not a palindrome. If it is possible, we must also...

Practice › Codeforces Solutions › Educational Codeforces Round 166 (Rated for Div. 2) ›

CF 1976D - Invertible Bracket Sequences

CF 1976D - Invertible Bracket Sequences Rating: 2000 Tags: binary search, combinatorics, data structures, divide and conquer, implementation, two pointers Solve time: 5m 14s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 947 (Div. 1 + Div. 2) ›

CF 1975F - Set

CF 1975F - Set Rating: 2600 Tags: bitmasks, brute force, combinatorics, dfs and similar, divide and conquer, dp, math Solve time: 5m 17s Verified: no Solution

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3864 - Minimum Cost to Partition a Binary String

LeetCode Problem 3864 Difficulty: 🔴 Hard Topics: String, Divide and Conquer, Prefix Sum Solution LeetCode 3864 - Minimum Cost to Partition a Binary String Problem Understanding We are given a binary string s , where each character represents whether an element is sensitive: '1' means the element is sensitive. '0' means the element is not sensitive. The entire string initially forms one segment. Every segment has a storage cost that...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3855 - Sum of K-Digit Numbers in a Range

LeetCode Problem 3855 Difficulty: 🔴 Hard Topics: Math, Divide and Conquer, Combinatorics, Number Theory Solution LeetCode 3855 - Sum of K-Digit Numbers in a Range Problem Understanding We are given three integers l , r , and k . For every digit position, we may independently choose any digit from the inclusive range [l, r] . We then form all possible numbers consisting of exactly k digits. A key detail...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3759 - Count Elements With at Least K Greater Values

LeetCode Problem 3759 Difficulty: 🟡 Medium Topics: Array, Binary Search, Divide and Conquer, Sorting, Quickselect Solution Problem Understanding The problem asks us to count how many elements in an array have at least k values that are strictly greater than them. More concretely, for every element nums[i] , we need to determine how many numbers in the array are larger than nums[i] . If that count is at least k...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3841 - Palindromic Path Queries in a Tree

LeetCode Problem 3841 Difficulty: 🔴 Hard Topics: Array, String, Divide and Conquer, Tree, Segment Tree Solution LeetCode 3841: Palindromic Path Queries in a Tree Problem Understanding We are given a tree with n nodes. Each node stores a lowercase English letter. The tree is undirected and connected, so there is exactly one simple path between any two nodes. The problem supports two kinds of operations: Update Change the character assigned...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3749 - Evaluate Valid Expressions

LeetCode Problem 3749 Difficulty: 🔴 Hard Topics: Hash Table, Math, String, Divide and Conquer, Stack Solution Problem Understanding The problem presents a simplified version of evaluating nested mathematical expressions in string format. The input expression is either a single integer literal, which may be negative, or a nested operation of the form op(a,b) where op is one of the four basic arithmetic operations: add , sub , mul , or...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3826 - Minimum Partition Score

LeetCode Problem 3826 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Dynamic Programming, Queue, Prefix Sum, Monotonic Queue Solution LeetCode 3826 - Minimum Partition Score Problem Understanding We are given an array nums and must divide it into exactly k contiguous subarrays. For every subarray, we first compute its sum: $$\text{sumArr} = \sum \text{elements in the subarray}$$ Its value is then defined as: $$\text{value} = \frac{\text{sumArr} \cdot (\text{sumArr}+1)}{2}$$ The score...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3739 - Count Subarrays With Majority Element II

LeetCode Problem 3739 Difficulty: 🔴 Hard Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Prefix Sum Solution Here’s a complete, detailed technical solution guide for LeetCode 3739 - Count Subarrays With Majority Element II following your requested format. Problem Understanding The problem asks us to count the number of contiguous subarrays in which a given target element is the majority element . A majority element is one...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3737 - Count Subarrays With Majority Element I

LeetCode Problem 3737 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Counting, Prefix Sum Solution Here is a comprehensive, detailed reference guide for LeetCode 3737 - Count Subarrays With Majority Element I , following your formatting requirements exactly. Problem Understanding The problem provides an integer array nums and a target integer. The goal is to count the number of subarrays in which the target...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3721 - Longest Balanced Subarray II

LeetCode Problem 3721 Difficulty: 🔴 Hard Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Prefix Sum Solution Problem Understanding The problem requires us to find the length of the longest subarray in an integer array nums where the count of distinct even numbers equals the count of distinct odd numbers . A subarray is a contiguous section of the array, and “distinct” means that duplicate values are counted only...

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3537 - Fill a Special Grid

LeetCode Problem 3537 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Matrix Solution Problem Understanding The problem asks us to construct a structured $2^n \times 2^n$ matrix filled with all integers from $0$ to $4^n - 1$, arranged in a very specific recursive ordering constraint across quadrants. A grid is considered special if it satisfies two key properties. First, there is a strict ordering between its four quadrants: every value...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3655 - XOR After Range Multiplication Queries II

LeetCode Problem 3655 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer Solution Problem Understanding We are given an array nums and a list of queries. Each query has the form: [li, ri, ki, vi] For a query, we start at index li and repeatedly jump forward by ki until we pass ri . Every visited position is multiplied by vi , and the result is taken modulo 10^9 + 7...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3653 - XOR After Range Multiplication Queries I

LeetCode Problem 3653 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Simulation Solution LeetCode 3653 - XOR After Range Multiplication Queries I Problem Understanding We are given an integer array nums and a list of queries. Each query has the form: [li, ri, ki, vi] For a query, we start at index li and repeatedly move forward by ki positions until we exceed ri . Every visited index is updated...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3636 - Threshold Majority Queries

LeetCode Problem 3636 Difficulty: 🔴 Hard Topics: Array, Hash Table, Binary Search, Divide and Conquer, Counting, Prefix Sum Solution Problem Understanding The problem asks us to process multiple queries on a given array nums where each query specifies a subarray defined by [li, ri] and a threshold . For each query, we need to find an element in the subarray that appears at least threshold times. If multiple elements meet...

Practice › Codeforces Solutions › Codeforces Round 261 (Div. 2) ›

CF 459D - Pashmak and Parmida's problem

CF 459D - Pashmak and Parmida's problem Rating: 1800 Tags: data structures, divide and conquer, sortings Solve time: 2m 17s Verified: yes Solution Problem Understanding We are given an array a[1..n] . For every position i , define the value L[i] = number of occurrences of a[i] in the prefix [1..i] . For every position j , define R[j] = number of occurrences of a[j] in the suffix [j..n] ....

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 1 ›

CF 452F - Permutation

CF 452F - Permutation Rating: 2700 Tags: data structures, divide and conquer, hashing Solve time: 2m 37s Verified: no Solution Problem Understanding The permutation contains every value from 1 to n exactly once. We need to determine whether there exist two distinct values a and b such that their arithmetic mean $$\frac{a+b}{2}$$ appears somewhere between them in the permutation order. Since the mean must itself be an integer in the...

Practice › Codeforces Solutions ›

Codeforces Round 274 (Div. 1)

Codeforces Round 274 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 2600-2800 | Time: 7m 16s Problem Name Rating Tags Solve Time Verified D Parcels 2600 dp, graphs 1m 52s ✓ E Parking Lot 2800 data-structures, divide-and-conquer 5m 24s ✗

Practice › Codeforces Solutions › Codeforces Round 134 (Div. 1) ›

CF 217C - Formurosa

CF 217C - Formurosa Rating: 2600 Tags: divide and conquer, dp, expression parsing Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given a Boolean formula consisting of constants 0 and 1, unknown variables denoted by ? , and the logical operators AND ( & ), OR ( | ), and XOR ( ^ ). Each ? corresponds to one of the n bacterial colonies, and the scientists...

Practice › Codeforces Solutions › Codeforces Round 245 (Div. 1) ›

CF 429D - Tricky Function

CF 429D - Tricky Function Rating: 2200 Tags: data structures, divide and conquer, geometry Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given an array of integers a with n elements. The task is to select two distinct indices i and j and compute a function f(i, j) that combines both the squared distance between the indices and the squared sum of the elements strictly between them....

Practice › Codeforces Solutions ›

Codeforces Round 190 (Div. 1)

Codeforces Round 190 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 2/2 | Rating range: 2100-2600 | Time: 5m 17s Problem Name Rating Tags Solve Time Verified C Ciel the Commander 2100 constructive-algorithms, dfs-and-similar, divide-and-conquer 3m 39s ✓ E Ciel and Gondolas 2600 data-structures, divide-and-conquer, dp 1m 38s ✓

Practice › Codeforces Solutions ›

Codeforces Round 240 (Div. 1)

Codeforces Round 240 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1400-3200 | Time: 8m 52s Problem Name Rating Tags Solve Time Verified A Mashmokh and Numbers 1500 constructive-algorithms, number-theory 2m 6s ✗ B Mashmokh and ACM 1400 combinatorics, dp, number-theory 1m 21s ✓ C Mashmokh and Reverse Operation 2100 combinatorics, divide-and-conquer 1m 40s ✓ D Mashmokh and Water Tanks 2300 binary-search, data-structures, greedy...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2426 - Number of Pairs Satisfying Inequality

LeetCode Problem 2426 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 2426 - Number of Pairs Satisfying Inequality Problem Understanding We are given two integer arrays, nums1 and nums2 , of the same length n , along with an integer diff . We must count how many index pairs (i, j) satisfy both: i < j nums1[i]...

Practice › Codeforces Solutions ›

Codeforces Round 124 (Div. 1)

Codeforces Round 124 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1100-2600 | Time: 6m 40s Problem Name Rating Tags Solve Time Verified A Lexicographically Maximum Subsequence 1100 greedy, strings 1m 2s ✓ B Infinite Maze 2000 dfs-and-similar, graphs 1m 39s ✓ C Paint Tree 2200 constructive-algorithms, divide-and-conquer, geometry 1m 40s ✗ E Opening Portals 2600 dsu, graphs, shortest-paths 2m 19s ✓

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2179 - Count Good Triplets in an Array

LeetCode Problem 2179 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding In this problem, we are given two arrays, nums1 and nums2 , each containing every integer from 0 to n - 1 exactly once. In other words, both arrays are permutations of the same set of values. We need to count how many triplets (x,...

Practice › Codeforces Solutions › Coder-Strike 2014 - Round 2 ›

CF 413E - Maze 2D

CF 413E - Maze 2D Rating: 2200 Tags: data structures, divide and conquer Solve time: 1m 21s Verified: yes Solution Problem Understanding We are working on a very narrow grid: only two rows, but a large number of columns. Each cell in this 2 by n strip is either free or blocked. Movement is allowed only between side-adjacent free cells, so the grid naturally forms a graph where each cell...

Practice › Codeforces Solutions › Croc Champ 2013 - Round 2 ›

CF 293E - Close Vertices

CF 293E - Close Vertices Rating: 2700 Tags: data structures, divide and conquer, trees Solve time: 4m 5s Verified: yes Solution Problem Understanding We are given a weighted tree with n vertices. Every edge contributes two different quantities to a path. The first quantity is the path length, meaning the number of edges on the path. The second quantity is the path weight, meaning the sum of edge weights on...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2343 - Query Kth Smallest Trimmed Number

LeetCode Problem 2343 Difficulty: 🟡 Medium Topics: Array, String, Divide and Conquer, Sorting, Heap (Priority Queue), Radix Sort, Quickselect Solution Problem Understanding This problem provides a list of numbers represented as strings, all of equal length. The task is to answer multiple queries, where each query asks for the index of the k-th smallest number after trimming every number in the list to its last trimi digits. Importantly, if two...

Practice › Codeforces Solutions › Codeforces Round 240 (Div. 1) ›

CF 414C - Mashmokh and Reverse Operation

CF 414C - Mashmokh and Reverse Operation Rating: 2100 Tags: combinatorics, divide and conquer Solve time: 1m 40s Verified: yes Solution Problem Understanding We are given an array of length $2^n$, where $n$ is at most 20, and a sequence of queries. Each query specifies a number $q_i$, which tells us to repeatedly split the array into blocks of size $2^{q_i}$, reverse each block, and then join the blocks back...

Practice › Codeforces Solutions › Codeforces Round 107 (Div. 1) ›

CF 150E - Freezing with Style

CF 150E - Freezing with Style Rating: 3000 Tags: binary search, data structures, divide and conquer, trees Solve time: 2m 49s Verified: yes Solution Problem Understanding We are given a tree with n junctions and n - 1 roads. Every road has an integer beauty value. We must choose two junctions so that the path between them contains between l and r edges inclusive. Among all such paths, we want...

Practice › Codeforces Solutions ›

Codeforces Round 145 (Div. 2, ACM-ICPC Rules)

Codeforces Round 145 (Div. 2, ACM-ICPC Rules) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 1000-2000 | Time: 9m 42s Problem Name Rating Tags Solve Time Verified B Reading 1000 sortings 1m 19s ✓ C Weather 1300 dp, implementation 1m 27s ✓ F Fence 1800 dp 1m 5s ✗ G Practice 1600 constructive-algorithms, divide-and-conquer, implementation 2m 54s ✗ H Merging Two Decks 2000 constructive-algorithms, greedy 2m...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2407 - Longest Increasing Subsequence II

LeetCode Problem 2407 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Dynamic Programming, Binary Indexed Tree, Segment Tree, Queue, Monotonic Queue Solution Problem Understanding The problem asks us to find the length of the longest subsequence in an integer array nums such that the subsequence is strictly increasing and the difference between consecutive elements does not exceed a given integer k . A subsequence is formed by deleting zero or...

Practice › Codeforces Solutions › Codeforces Round 124 (Div. 1) ›

CF 196C - Paint Tree

CF 196C - Paint Tree Rating: 2200 Tags: constructive algorithms, divide and conquer, geometry, sortings, trees Solve time: 1m 40s Verified: no Solution Problem Understanding We are asked to embed a tree onto a set of points on a plane in such a way that tree edges correspond to straight line segments connecting the points. Each vertex of the tree must be mapped to a distinct point, and for any...

Practice › Codeforces Solutions ›

Codeforces Round 199 (Div. 2)

Codeforces Round 199 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1200-2400 | Time: 16m 31s Problem Name Rating Tags Solve Time Verified A Xenia and Divisors 1200 greedy, implementation 6m 2s ✗ C Cupboard and Balloons 1900 geometry 5m 17s ✓ E Xenia and Tree 2400 data-structures, divide-and-conquer, trees 5m 12s ✓

Practice › Codeforces Solutions › Codeforces Round 199 (Div. 2) ›

CF 342E - Xenia and Tree

CF 342E - Xenia and Tree Rating: 2400 Tags: data structures, divide and conquer, trees Solve time: 5m 12s Verified: yes Solution Problem Understanding We are given a tree of n nodes, rooted conceptually at node 1, which starts painted red. All other nodes are blue. We have to handle two types of queries: first, paint a blue node red; second, for a given node, report the distance to the...

Practice › Codeforces Solutions › Codeforces Round 144 (Div. 1) ›

CF 232C - Doe Graphs

CF 232C - Doe Graphs Rating: 2600 Tags: constructive algorithms, divide and conquer, dp, graphs, shortest paths Solve time: 2m 23s Verified: yes Solution Problem Understanding The graph family is built recursively. D(0) is a single vertex. D(1) is a single edge. For every larger order, D(n) is formed by taking a copy of D(n-1) and a shifted copy of D(n-2) , then connecting them with two extra edges. The...

Practice › Codeforces Solutions › Codeforces Round 145 (Div. 2, ACM-ICPC Rules) ›

CF 234G - Practice

CF 234G - Practice Rating: 1600 Tags: constructive algorithms, divide and conquer, implementation Solve time: 2m 54s Verified: no Solution Problem Understanding We are given a team of n football players, each with a unique number from 1 to n . The coach wants to organize practice games so that every pair of players has faced each other on opposing teams at least once. Each practice splits all players into...

Practice › LeetCode › LeetCode 27xx ›

LeetCode 2792 - Count Nodes That Are Great Enough

LeetCode Problem 2792 Difficulty: 🔴 Hard Topics: Divide and Conquer, Tree, Depth-First Search, Binary Tree Solution Problem Understanding The problem gives us the root of a binary tree and an integer k . We must determine how many nodes in the tree are considered "great enough". A node is great enough if two conditions are satisfied: Its subtree contains at least k nodes. Its value is greater than the values...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1985 - Find the Kth Largest Integer in the Array

LeetCode Problem 1985 Difficulty: 🟡 Medium Topics: Array, String, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect Solution Problem Understanding This problem asks us to find the kth largest value among a list of integers that are represented as strings. Each element in nums is a non-negative integer encoded as a string with no leading zeros, and we are required to return the kth largest value according to numeric order,...

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161C - Abracadabra

CF 161C - Abracadabra Rating: 2400 Tags: divide and conquer Solve time: 2m 37s Verified: yes Solution Problem Understanding The infinite string in this problem is built recursively. Start with: S1 = "a" S2 = "aba" S3 = "abacaba" S4 = "abacabadabacaba" In general: Sk = Sk-1 + kth_character + Sk-1 The alphabet contains 36 symbols: a..z, 0..9 The full string after 30 steps has length: $|S_k| = 2^k -...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3165 - Maximum Sum of Subsequence With Non-adjacent Elements

LeetCode Problem 3165 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Dynamic Programming, Segment Tree Solution LeetCode 3165 - Maximum Sum of Subsequence With Non-adjacent Elements Problem Understanding This problem asks us to process a sequence of update queries on an array. After each update, we must compute the maximum possible sum of a subsequence where no two selected elements are adjacent in the array. The key detail is that...

Practice › LeetCode › LeetCode 25xx ›

LeetCode 2519 - Count the Number of K-Big Indices

LeetCode Problem 2519 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 2519 - Count the Number of K-Big Indices Problem Understanding This problem asks us to determine how many indices in an array satisfy a very specific condition related to smaller values on both sides. For an index i to be considered k-big , two separate requirements...

Practice › Codeforces Solutions › Codeforces Round 190 (Div. 1) ›

CF 321E - Ciel and Gondolas

CF 321E - Ciel and Gondolas Rating: 2600 Tags: data structures, divide and conquer, dp Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a sequence of people standing in a line, indexed from 1 to n. We must split this line into k consecutive groups. Each group is formed by taking a prefix of the remaining queue, so the partition is fully described by cutting the...

Practice › Codeforces Solutions ›

Codeforces Round 134 (Div. 1)

Codeforces Round 134 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1200-2900 | Time: 12m 51s Problem Name Rating Tags Solve Time Verified A Ice Skating 1200 brute-force, dfs-and-similar, dsu 1m 15s ✓ C Formurosa 2600 divide-and-conquer, dp, expression-parsing 1m 20s ✓ D Bitonix' Patrol 2900 bitmasks, brute-force, combinatorics 3m 51s ✗ E Alien DNA 2800 data-structures, dsu, trees 6m 25s ✓

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3109 - Find the Index of Permutation

LeetCode Problem 3109 Difficulty: 🟡 Medium Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem gives us a permutation perm of the integers [1, 2, ..., n] . A permutation is simply an arrangement of all numbers from 1 to n where each number appears exactly once. We are asked to determine the lexicographic index of this permutation...

Practice › LeetCode › LeetCode 26xx ›

LeetCode 2613 - Beautiful Pairs

LeetCode Problem 2613 Difficulty: 🔴 Hard Topics: Array, Math, Divide and Conquer, Geometry, Sorting, Ordered Set Solution Problem Understanding The problem asks us to find a beautiful pair of indices (i, j) in two integer arrays nums1 and nums2 of equal length. A pair (i, j) is beautiful if it minimizes the sum of the absolute differences between the corresponding elements: |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| among all...

Practice › Codeforces Solutions › Codeforces Round 190 (Div. 1) ›

CF 321C - Ciel the Commander

CF 321C - Ciel the Commander Rating: 2100 Tags: constructive algorithms, dfs and similar, divide and conquer, greedy, trees Solve time: 3m 39s Verified: yes Solution Problem Understanding We are given a tree with n cities connected by n-1 roads. Each city must be assigned an officer with a rank from 'A' (highest) to 'Z' (lowest). The constraint is that if two cities share the same officer rank, the path...

Practice › Codeforces Solutions › Codeforces Round 114 (Div. 1) ›

CF 167D - Wizards and Roads

CF 167D - Wizards and Roads Rating: 3000 Tags: data structures, divide and conquer, graph matchings, graphs, greedy Solve time: 2m 8s Verified: yes Solution Problem Understanding We are given a set of cities on the plane. Every city has a unique x coordinate and a unique y coordinate. The first k cities are given explicitly, and the remaining cities are generated by two linear recurrences. For every query interval...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 240 - Search a 2D Matrix II

LeetCode Problem 240 Difficulty: 🟡 Medium Topics: Array, Binary Search, Divide and Conquer, Matrix Solution Problem Understanding The problem asks us to determine whether a given integer target exists inside an m x n matrix. Unlike a completely unsorted matrix, this matrix has two important ordering guarantees: Each row is sorted in ascending order from left to right. Each column is sorted in ascending order from top to bottom. We...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1649 - Create Sorted Array through Instructions

LeetCode Problem 1649 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to simulate building a sorted array incrementally. We process the instructions array from left to right, and for each value, we insert it into a container called nums while maintaining sorted order. However, the actual insertion is not the difficult part....

Practice › Codeforces Solutions › School Regional Team Contest, Saratov, 2011 ›

CF 120J - Minimum Sum

CF 120J - Minimum Sum Rating: 1900 Tags: divide and conquer, geometry, sortings Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a set of points in two-dimensional space, where each point can be thought of as a vector from the origin. Each vector has two coordinates, x and y , and we are allowed to independently flip the sign of each coordinate. That is, for any...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1763 - Longest Nice Substring

LeetCode Problem 1763 Difficulty: 🟢 Easy Topics: Hash Table, String, Divide and Conquer, Bit Manipulation, Sliding Window Solution Problem Understanding The problem asks us to find the longest "nice" substring within a given string s . A substring is considered nice if for every letter it contains, both its lowercase and uppercase forms appear. For example, "aAa" is nice because it contains 'a' and 'A' . Conversely, "abA" is not...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 307 - Range Sum Query - Mutable

LeetCode Problem 307 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Design, Binary Indexed Tree, Segment Tree Solution Problem Understanding The problem asks us to design a mutable range sum data structure. We are given an integer array nums , and we must efficiently support two operations: Updating the value at a specific index. Querying the sum of elements within a range [left, right] . The important detail is that...

Practice › Codeforces Solutions › Codeforces Beta Round 62 ›

CF 68D - Half-decay tree

CF 68D - Half-decay tree Rating: 2500 Tags: data structures, divide and conquer, dp, math, probabilities Solve time: 2m 50s Verified: yes Solution Problem Understanding We have a complete binary tree of height h . Every vertex may store some number of electrons, and queries gradually add more electrons to vertices. A decay operation chooses one leaf uniformly at random and deletes every edge on the path from the root...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 889 - Construct Binary Tree from Preorder and Postorder Traversal

LeetCode Problem 889 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree Solution Problem Understanding The problem gives us two traversal orders of the same binary tree: preorder , which visits nodes in the order: root → left subtree → right subtree postorder , which visits nodes in the order: left subtree → right subtree → root Our task is to reconstruct and return the binary...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 912 - Sort an Array

LeetCode Problem 912 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort Solution Problem Understanding The problem asks us to sort an integer array in ascending order without using any built in sorting functions. The result must contain the same elements as the input, but arranged from smallest to largest. The input is an array nums containing integers. These...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST

LeetCode Problem 1569 Difficulty: 🔴 Hard Topics: Array, Math, Divide and Conquer, Dynamic Programming, Tree, Union-Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree Solution Problem Understanding The problem gives us a permutation of integers from 1 to n , and we insert the numbers into an initially empty Binary Search Tree (BST) in the exact order they appear in the array. A BST has the following property: Values smaller than...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 918 - Maximum Sum Circular Subarray

LeetCode Problem 918 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Dynamic Programming, Queue, Monotonic Queue Solution Problem Understanding The problem asks for the maximum sum of a subarray in a circular array . In simpler terms, we are given a list of integers nums where the end of the list wraps around to the start. We need to find a contiguous section of this list that has the highest...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 427 - Construct Quad Tree

LeetCode Problem 427 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Tree, Matrix Solution Problem Understanding The problem asks us to convert a binary matrix into a Quad-Tree representation. A Quad-Tree is a recursive tree structure where every internal node has exactly four children, each representing one quadrant of the current square region. The input is an n x n matrix called grid , where every value is either 0...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 372 - Super Pow

LeetCode Problem 372 Difficulty: 🟡 Medium Topics: Math, Divide and Conquer Solution Problem Understanding The problem asks us to compute: $a^b \bmod 1337$ The complication is that the exponent b is extremely large. Instead of being given as a normal integer, it is provided as an array of digits. For example, if: b = [1, 0, 2, 4] then the exponent actually represents the number: 1024 The goal is to...

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Finals

Yandex.Algorithm 2011: Finals Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 2200-2700 | Time: 11m 24s Problem Name Rating Tags Solve Time Verified A Domino 2400 brute-force, implementation 2m 46s ✗ B Superset 2300 constructive-algorithms, divide-and-conquer 2m 12s ✓ C Winning Strategy 2400 binary-search, graphs, math 1m 44s ✓ D Robot in Basement 2700 bitmasks, brute-force, implementation 2m 39s ✓ E Leaders 2200 dfs-and-similar, dsu, graphs 2m...

Practice › LeetCode › LeetCode 20xx ›

LeetCode 2031 - Count Subarrays With More Ones Than Zeros

LeetCode Problem 2031 Difficulty: 🟡 Medium Topics: Array, Hash Table, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding This problem asks us to count all subarrays of a binary array nums that contain more 1 s than 0 s. In other words, for any contiguous slice of the array, if the number of 1 s exceeds the number of 0 s,...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 395 - Longest Substring with At Least K Repeating Characters

LeetCode Problem 395 Difficulty: 🟡 Medium Topics: Hash Table, String, Divide and Conquer, Sliding Window Solution Problem Understanding The problem asks us to find the length of the longest substring in which every character appears at least k times. A substring is a contiguous sequence of characters inside the original string. For any candidate substring, we must verify that every distinct character inside that substring has frequency greater than or...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 493 - Reverse Pairs

LeetCode Problem 493 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to count how many pairs of indices (i, j) satisfy two conditions: i < j nums[i] > 2 * nums[j] These pairs are called reverse pairs. Unlike the classic inversion count problem, where we check whether nums[i] > nums[j] , this...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 347 - Top K Frequent Elements

LeetCode Problem 347 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect Solution Problem Understanding The problem asks us to return the k most frequently occurring elements from an integer array. We are given an array nums , which may contain duplicates, and an integer k . Our task is to identify which values appear most often and return exactly k...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1382 - Balance a Binary Search Tree

LeetCode Problem 1382 Difficulty: 🟡 Medium Topics: Divide and Conquer, Greedy, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Here is a complete, detailed technical solution guide for LeetCode 1382 - Balance a Binary Search Tree , following all your formatting rules. Problem Understanding The problem asks us to take a binary search tree (BST) that may be unbalanced and produce a new BST that is balanced while preserving...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 315 - Count of Smaller Numbers After Self

LeetCode Problem 315 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to compute, for every element in the array, how many elements to its right are strictly smaller than it. Given an array nums , we must return another array counts of the same length. For each index i , counts[i] represents...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 327 - Count of Range Sum

LeetCode Problem 327 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 327 - Count of Range Sum Problem Understanding This problem asks us to count how many subarrays have sums that fall within a given inclusive range [lower, upper] . A range sum S(i, j) represents the sum of all elements from index i through index j...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 558 - Logical OR of Two Binary Grids Represented as Quad-Trees

LeetCode Problem 558 Difficulty: 🟡 Medium Topics: Divide and Conquer, Tree Solution Problem Understanding This problem gives us two Quad-Trees, where each tree represents a binary matrix containing only 0 s and 1 s. Our goal is to compute the logical bitwise OR of the two matrices and return the result as another Quad-Tree. A Quad-Tree is a recursive spatial data structure. Every node represents a square region of the...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 106 - Construct Binary Tree from Inorder and Postorder Traversal

LeetCode Problem 106 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree Solution Problem Understanding The problem provides two traversal orders of the same binary tree: inorder , which follows the order: left subtree, root, right subtree postorder , which follows the order: left subtree, right subtree, root We must reconstruct the original binary tree and return its root node. The key challenge is understanding how...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 109 - Convert Sorted List to Binary Search Tree

LeetCode Problem 109 Difficulty: 🟡 Medium Topics: Linked List, Divide and Conquer, Tree, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us the head of a singly linked list whose values are already sorted in ascending order. We must convert this linked list into a height balanced Binary Search Tree, usually abbreviated as BST. A Binary Search Tree has the property that: Every node in the left...

Practice › Codeforces Solutions › Codeforces Beta Round 79 (Div. 1 Only) ›

CF 101E - Candies and Stones

CF 101E - Candies and Stones Rating: 2500 Tags: divide and conquer, dp Solve time: 3m 26s Verified: no Solution Problem Understanding Gerald repeatedly removes either one candy or one stone. After every move, Mike looks at how many candies and stones Gerald has already eaten. If Gerald has eaten a candies and b stones so far, Mike awards $$f(a,b) = (x_a + y_b) \bmod p$$ points. The game starts...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal

LeetCode Problem 105 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree Solution Problem Understanding The problem is asking us to reconstruct a binary tree given two traversal orders: preorder and inorder . In a preorder traversal, nodes are visited in the order: root, left subtree, right subtree. In an inorder traversal, nodes are visited in the order: left subtree, root, right subtree. Given these two...

Practice › Codeforces Solutions › Codeforces Beta Round 19 ›

CF 19E - Fairy

CF 19E - Fairy Rating: 2900 Tags: dfs and similar, divide and conquer, dsu Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given an undirected graph. Each edge represents a segment drawn between two points. We may erase exactly one edge, and after removing it we want the remaining graph to become bipartite. A graph is bipartite if we can color every vertex using two colors such...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 148 - Sort List

LeetCode Problem 148 Difficulty: 🟡 Medium Topics: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort Solution Problem Understanding The problem asks us to sort a singly linked list in ascending order and return the head of the sorted list. The input is the head node of a linked list. Each node contains an integer value and a pointer to the next node. Unlike arrays, linked lists do not...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1738 - Find Kth Largest XOR Coordinate Value

LeetCode Problem 1738 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Bit Manipulation, Sorting, Heap (Priority Queue), Matrix, Prefix Sum, Quickselect Solution Problem Understanding The problem asks us to compute the XOR coordinate value for each element in a given 2D matrix and then find the kth largest among them. Specifically, for a coordinate (a, b) , the value is defined as the XOR of all elements in the submatrix...

Practice › Codeforces Solutions › Codeforces Beta Round 9 (Div. 2 Only) ›

CF 9D - How many trees?

CF 9D - How many trees? Rating: 1900 Tags: combinatorics, divide and conquer, dp Solve time: 1m 13s Verified: yes Solution Problem Understanding We are asked to count the number of distinct binary search trees (BSTs) that have exactly n nodes labeled from 1 to n , with the additional constraint that the height of each tree is at least h . Height here is defined as the number of...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 169 - Majority Element

LeetCode Problem 169 Difficulty: 🟢 Easy Topics: Array, Hash Table, Divide and Conquer, Sorting, Counting Solution Problem Understanding The problem asks us to identify the majority element in a given array of integers nums . The majority element is defined as the number that appears more than half of the times in the array, i.e., more than ⌊n / 2⌋ times where n is the length of the array. The...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 108 - Convert Sorted Array to Binary Search Tree

LeetCode Problem 108 Difficulty: 🟢 Easy Topics: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us a sorted integer array nums in strictly increasing order and asks us to convert it into a height-balanced binary search tree (BST) . A binary search tree is a binary tree where: Every node in the left subtree contains values smaller than the current node. Every...

Practice › Codeforces Solutions › Codeforces Beta Round 88 ›

CF 117D - Not Quick Transformation

CF 117D - Not Quick Transformation Rating: 2500 Tags: divide and conquer, math Solve time: 2m 20s Verified: yes Solution Problem Understanding We start with the array [1, 2, 3, ..., n] . A recursive transformation rearranges it by repeatedly taking all elements at odd positions, transforming that subarray, then taking all elements at even positions and transforming that subarray. For example: F([1,2,3,4,5,6,7,8]) becomes F([1,3,5,7]) + F([2,4,6,8]) and each half...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 218 - The Skyline Problem

LeetCode Problem 218 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Binary Indexed Tree, Segment Tree, Sweep Line, Sorting, Heap (Priority Queue), Ordered Set Solution Problem Understanding The Skyline Problem asks us to compute the visible outer contour formed by a collection of rectangular buildings when viewed from far away. Each building is represented by three integers: a left x-coordinate, a right x-coordinate, and a height. The buildings sit on...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 973 - K Closest Points to Origin

LeetCode Problem 973 Difficulty: 🟡 Medium Topics: Array, Math, Divide and Conquer, Geometry, Sorting, Heap (Priority Queue), Quickselect Solution Problem Understanding This problem asks us to find the k points that are closest to the origin (0,0) from a list of 2D points. Each point is given as a pair [x, y] , and the distance is defined using the Euclidean formula, sqrt(x^2 + y^2) . The input consists of...

Practice › Codeforces Solutions ›

Codeforces Beta Round 62

Codeforces Beta Round 62 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1100-2900 | Time: 26m 18s Problem Name Rating Tags Solve Time Verified A Irrational problem 1100 implementation, number-theory 7m 4s ✓ B Energy exchange 1600 binary-search 7m 4s ✓ C Synchrophasotron 2200 brute-force 7m 3s ✓ D Half-decay tree 2500 data-structures, divide-and-conquer, dp 2m 50s ✓ E Contact 2900 geometry 2m 17s ✓

Practice › LeetCode › LeetCode 07xx ›

LeetCode 761 - Special Binary String

LeetCode Problem 761 Difficulty: 🔴 Hard Topics: String, Divide and Conquer, Sorting Solution Problem Understanding The problem asks us to manipulate a special binary string to produce the lexicographically largest possible string. A special binary string has two properties: it contains equal numbers of 1 s and 0 s, and at every point in the string, the number of 1 s is at least as many as the number of...

Practice › Codeforces Solutions › Codeforces Beta Round 88 ›

CF 117E - Tree or not Tree

CF 117E - Tree or not Tree Rating: 2900 Tags: data structures, divide and conquer, graphs, implementation, trees Solve time: 3m 13s Verified: yes Solution Problem Understanding The graph has exactly n vertices and n edges. A connected graph with n vertices and n edges contains exactly one simple cycle. Every other edge belongs to a tree attached to that cycle. Initially every edge is turned off. A query picks...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 23 - Merge k Sorted Lists

LeetCode Problem 23 Difficulty: 🔴 Hard Topics: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort Solution Problem Understanding The problem gives us an array of k sorted linked lists. Each linked list is already sorted in ascending order, and our task is to combine all of them into one single sorted linked list. A linked list node contains a value and a pointer to the next node. The...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 932 - Beautiful Array

LeetCode Problem 932 Difficulty: 🟡 Medium Topics: Array, Math, Divide and Conquer Solution Problem Understanding The problem asks us to construct a permutation of the integers from 1 to n such that the array satisfies a special condition. Specifically, for every pair of indices i < j , there must not exist any index k between them where: $2 \cdot nums[k] = nums[i] + nums[j]$ This condition means that no...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 324 - Wiggle Sort II

LeetCode Problem 324 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Greedy, Sorting, Quickselect Solution Problem Understanding The problem asks us to rearrange an array so that it follows a strict alternating pattern: nums[0] < nums[1] nums[1] > nums[2] nums[2] < nums[3] and so on. This pattern is called a wiggle sequence because the values repeatedly go up and down. The input is an integer array nums , and we...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1756 - Design Most Recently Used Queue

LeetCode Problem 1756 Difficulty: 🟡 Medium Topics: Array, Linked List, Divide and Conquer, Design, Simulation, Doubly-Linked List Solution Problem Understanding The problem asks us to design a special queue called an "Most Recently Used Queue", abbreviated as MRUQueue. Initially, the queue contains the integers from 1 to n in increasing order. The key operation is fetch(k) , where k is 1-indexed. This operation does two things: It finds the kth...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1274 - Number of Ships in a Rectangle

LeetCode Problem 1274 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Interactive Solution Problem Understanding The problem presents an interactive scenario where ships are placed at integer coordinates on a Cartesian plane. You do not know their positions, and each coordinate contains at most one ship. You are given two points representing the bottom-left and top-right corners of a rectangle, and you need to determine the number of ships contained...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 215 - Kth Largest Element in an Array

LeetCode Problem 215 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect Solution Problem Understanding The problem asks us to find the kth largest element in an unsorted integer array. The important detail is that we are looking for the element that would appear in the kth position if the array were sorted in descending order. We are not looking for the kth distinct value. For...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 654 - Maximum Binary Tree

LeetCode Problem 654 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Stack, Tree, Monotonic Stack, Binary Tree Solution Problem Understanding The problem asks us to construct a maximum binary tree from a given integer array nums with unique elements. A maximum binary tree is a binary tree where each node is the maximum element of the subarray it represents. Specifically, the root of the tree is the largest element in...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Finals ›

CF 97B - Superset

CF 97B - Superset Rating: 2300 Tags: constructive algorithms, divide and conquer Solve time: 2m 12s Verified: yes Solution Problem Understanding We start with a set of distinct lattice points on the plane. We may add more points, and the final set must satisfy a geometric condition for every pair of points. Take any two points. If they already share the same x-coordinate or the same y-coordinate, they are automatically...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 53 - Maximum Subarray

LeetCode Problem 53 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Dynamic Programming Solution LeetCode 53, Maximum Subarray Problem Understanding The problem gives an integer array nums and asks us to find a contiguous subarray that has the largest possible sum. A subarray means the elements must appear next to each other in the original array. We are not allowed to rearrange elements or skip positions arbitrarily. The output is...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 4 - Median of Two Sorted Arrays

LeetCode Problem 4 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer Solution Median of Two Sorted Arrays Problem Understanding The problem gives two individually sorted integer arrays, nums1 and nums2 , with lengths m and n . The task is to compute the median of the combined sorted sequence formed by merging both arrays. The median is the middle value of a sorted sequence. If the total number...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 191 - Number of 1 Bits

LeetCode Problem 191 Difficulty: 🟢 Easy Topics: Divide and Conquer, Bit Manipulation Solution Problem Understanding The problem asks us to count how many bits are set to 1 in the binary representation of a positive integer n . A set bit is simply a bit whose value is 1 . For example, the number 11 in binary is: 1011 This binary representation contains three 1 bits, so the answer is...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 190 - Reverse Bits

LeetCode Problem 190 Difficulty: 🟢 Easy Topics: Divide and Conquer, Bit Manipulation Solution Problem Understanding The problem asks us to reverse the binary representation of a 32-bit integer . Instead of reversing the decimal digits of a number, we reverse the order of its individual bits. For example, suppose the binary representation of a number is: 00000010100101000001111010011100 After reversing all 32 bits, it becomes: 00111001011110000010100101000000 The resulting reversed binary value...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1008: Construct Binary Search Tree from Preorder Traversal

Problem Restatement We are given the preorder traversal of a binary search tree (BST) in an array preorder . We need to reconstruct the BST and return its root. Recall that in a BST, for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. In preorder traversal, we visit the root before the left and right subtrees. The official constraints...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 889: Construct Binary Tree from Preorder and Postorder Traversal

Problem Restatement We are given two arrays: Array Meaning preorder Preorder traversal of a binary tree postorder Postorder traversal of the same binary tree The binary tree contains distinct values. We need to reconstruct and return one possible binary tree. If multiple valid trees exist, returning any one of them is accepted. The problem guarantees that both traversals come from the same binary tree. Preorder traversal visits nodes in this...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 912: Sort an Array

Problem Restatement We are given an integer array nums . Return the array sorted in ascending order. The problem requires solving this without using built-in sorting functions, in O(n log n) time, with as little extra space as possible. Input and Output Item Meaning Input An integer array nums Output The same values sorted in ascending order Restriction Do not use built-in sorting functions Target time O(n log n) Function...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 761: Special Binary String

Problem Restatement A special binary string is a binary string with two properties: It has the same number of 1 s and 0 s. Every prefix has at least as many 1 s as 0 s. We are given a special binary string s . One move lets us choose two consecutive non-empty special substrings and swap them. We need to return the lexicographically largest string possible after applying any...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 932: Beautiful Array

Problem Restatement We are given an integer n . We need to return any array nums of length n such that: nums is a permutation of integers from 1 to n . For every i < j , there is no index k with i < k < j such that: 2 * nums[k] == nums[i] + nums[j] In other words, no middle-position value may be the arithmetic average of...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 654: Maximum Binary Tree

Problem Restatement We are given an array of distinct integers called nums . We must construct a binary tree using the following rules: The root is the maximum number in the array. The left subtree is built recursively from the elements to the left of the maximum number. The right subtree is built recursively from the elements to the right of the maximum number. Return the root of the constructed...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 395: Longest Substring with At Least K Repeating Characters

Problem Restatement We are given a string s and an integer k . We need to return the length of the longest substring where every character in that substring appears at least k times. A substring must be contiguous. If no valid substring exists, return 0 . The string contains only lowercase English letters. The length of s is at most 10^4 , and k can be larger than the...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 493: Reverse Pairs

Problem Restatement We are given an integer array nums . We need to count pairs of indices (i, j) such that: 0 <= i < j < nums.length and: nums[i] > 2 * nums[j] These are called reverse pairs. The input length can be up to 5 * 10^4 , and values may be negative or as large as 32-bit signed integers. Input and Output Item Meaning Input Integer array...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 241: Different Ways to Add Parentheses

Problem Restatement We are given a string expression containing: Non-negative integers Operators: + - * We need to compute all possible results from adding parentheses in every valid way. The answer may contain duplicate values if different parenthesizations produce the same result. LeetCode examples include: Input: expression = "2-1-1" Output: [0,2] and: Input: expression = "2*3-4*5" Output: [-34,-14,-10,-10,10] The expression length is at most 20 . Input and Output Item...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 215: Kth Largest Element in an Array

Problem Restatement We are given an integer array nums and an integer k . We need to return the k th largest element in the array. Important detail: this means the k th largest element in sorted order, not the k th distinct element. Duplicates count separately. The official constraints are 1 <= k <= nums.length <= 10^5 and -10^4 <= nums[i] <= 10^4 . Input and Output Item Meaning...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 148: Sort List

Problem Restatement We are given the head of a singly linked list. Return the list after sorting it in ascending order. The problem asks for an O(n log n) time solution. The follow-up asks whether we can sort the list with constant extra space. The number of nodes is in the range [0, 5 * 10^4] , and node values are between -10^5 and 10^5 . Examples Example 1: head...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 169: Majority Element

Problem Restatement We are given an integer array nums of size n . We need to return the majority element. The majority element is the value that appears more than: n // 2 times. The problem guarantees that a majority element always exists. LeetCode also asks whether we can solve it in linear time and constant extra space. Input and Output Item Meaning Input Integer array nums Output The majority...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 109: Convert Sorted List to Binary Search Tree

Problem Restatement We are given the head of a singly linked list whose values are sorted in ascending order. We need to convert this sorted linked list into a height-balanced binary search tree. The official problem defines a height-balanced binary tree as a binary tree where the depth difference between the two subtrees of every node never exceeds 1 . The resulting tree must satisfy the BST property: left subtree...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 108: Convert Sorted Array to Binary Search Tree

Problem Restatement We are given a sorted integer array nums in ascending order. We need to convert it into a height-balanced binary search tree. The official problem defines a height-balanced binary tree as a binary tree in which the depth difference between the two subtrees of every node is never more than 1 . The tree must also satisfy the binary search tree property: left subtree values < root value...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal

Problem Restatement We are given two integer arrays: inorder postorder Both arrays describe the same binary tree. inorder is the inorder traversal of the tree. postorder is the postorder traversal of the same tree. We need to construct and return the original binary tree. The values are unique, and both arrays are guaranteed to describe the same tree. The official constraints also say each value in postorder appears in inorder...

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 23: Merge k Sorted Lists

Problem Restatement We are given an array of linked lists: lists Each linked list is sorted in ascending order. We need to merge all linked lists into one sorted linked list and return its head. The constraints say: Constraint Value k == lists.length Number of linked lists 0 <= k <= 10^4 Number of lists 0 <= lists[i].length <= 500 Length of each list Total nodes across all lists At...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 427: Construct Quad Tree

Problem Restatement We are given an n x n grid containing only 0 and 1 . We need to build a quad tree that represents this grid. A quad tree is a tree where each internal node has exactly four children: Child Region topLeft upper-left quadrant topRight upper-right quadrant bottomLeft lower-left quadrant bottomRight lower-right quadrant Each node has two main fields: Field Meaning val True for 1 , False for...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 327: Count of Range Sum

Problem Restatement We are given an integer array nums and two integers lower and upper . A range sum is the sum of a contiguous subarray: S(i, j) = nums[i] + nums[i + 1] + ... + nums[j] where i <= j . We need to count how many range sums lie inside this inclusive range: lower <= S(i, j) <= upper The naive O(n^2) solution is too slow, so...

Wiki › Algorithms › 01. Searching and Sorting ›

7. Divide and Conquer Sorting

7. Divide and conquer sorting, 35 index slug name 181 merge-sort Merge Sort 182 top-down-merge-sort Top Down Merge Sort 183 bottom-up-merge-sort Bottom Up Merge Sort 184 natural-merge-sort Natural Merge Sort 185 in-place-merge-sort In Place Merge Sort 186 block-merge-sort Block Merge Sort 187 timsort Timsort 188 powersort Powersort 189 quicksort Quicksort 190 randomized-quicksort Randomized Quicksort 191 three-way-quicksort Three Way Quicksort 192 dual-pivot-quicksort Dual Pivot Quicksort 193 introsort Introsort 194 pdqsort Pattern...

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.4 Merge Sort

6.4 Merge Sort Merge sort is the standard example of divide and conquer sorting. It divides the input into two smaller arrays, sorts each half, and then merges the two sorted halves into one sorted output. The central operation is not the division step. It is the merge step, because merging is where the algorithm combines local order into global order. Problem You have an array A[0..n-1] . You want...

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.5 Quick Sort

6.5 Quick Sort Quick sort is a divide and conquer sorting algorithm based on partitioning. It chooses a pivot, rearranges the array so that smaller elements go to one side and larger elements go to the other side, and then recursively sorts the two partitions. Unlike merge sort, quick sort does most of its work before the recursive calls. Problem You have an array A[0..n-1] . You want an in-place...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.14 Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers. It is useful when the original problem has repeated structure and when the cost of combining subanswers is controlled. The pattern has three parts: divide: split the input into smaller pieces conquer: solve each piece recursively combine: merge the subanswers into the answer for the full input The key question is...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Merge Sort

Merge Sort Merge sort is a divide and conquer sorting algorithm. It splits the input into smaller parts, sorts each part recursively, then merges the sorted parts into a single sorted sequence. It guarantees stable ordering and predictable time complexity. It performs well on large datasets and external memory systems. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1]...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Sorted Matrix Search

Sorted Matrix Search Sorted matrix search finds a target in a matrix where each row and each column is sorted. Unlike saddleback search, this approach uses divide and conquer to recursively eliminate regions. Problem Given a matrix $A$ of size $n \times m$ such that: $$ A[i][j] \le A[i][j+1] $$ $$ A[i][j] \le A[i+1][j] $$ find a position $(i, j)$ such that: $$ A[i][j] = x $$ If no such...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Top Down Merge Sort

Top Down Merge Sort Top down merge sort is the canonical recursive form of merge sort. It starts from the full array, splits it into halves recursively until single elements remain, then merges upward. This form directly follows the divide and conquer recurrence and is the most common presentation in textbooks. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Two Dimensional Peak Finding

Two Dimensional Peak Finding Two dimensional peak finding finds a position in a matrix whose value is at least as large as its neighbors in four directions. Given a matrix $A$ of size $n \times m$, a position $(i, j)$ is a peak if: $A[i][j] \ge A[i-1][j]$ $A[i][j] \ge A[i+1][j]$ $A[i][j] \ge A[i][j-1]$ $A[i][j] \ge A[i][j+1]$ Out of bounds neighbors are treated as $-\infty$. Problem Given a matrix $A$, find...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Quicksort

Quicksort Quicksort is a divide and conquer sorting algorithm. It chooses a pivot value, partitions the array so that smaller elements go before the pivot and larger elements go after it, then recursively sorts both sides. It is one of the most important practical sorting algorithms because it is fast in memory, has good cache behavior, and usually needs only logarithmic stack space. Its main weakness is that bad pivot...

#divide-and-conquer

15.22 Common Bugs

15.13 Median of Medians

15.8 Fast Exponentiation

15.9 Divide-and-Conquer Dynamic Programming

15.16 Fast Fourier Transform

15.21 Testing Divide-and-Conquer Algorithms

15.12 Selection Algorithms

15.24 Case Studies

15.1 Recursion Trees

15.18 Closest Pair of Points

15.11 Cache-Oblivious Algorithms

15.23 Design Patterns

15.15 Binary Search on Answer

15.17 Offline Queries

15.19 Correctness Proofs

15.2 Master Theorem

15.10 Parallel Divide and Conquer

15.7 Strassen Multiplication

15.5 Closest Pair of Points

15.3 Merge Sort Revisited

15.6 Karatsuba Multiplication

15.14 Counting Inversions

15.4 Quick Sort Revisited

15.25 Exercises

15.20 Complexity Analysis

Chapter 15. Divide and Conquer

CF 2222G - Statistics on Tree

CF 480E - Parking Lot

CF 1956D - Nene and the Mex Operator

CF 1951E - No Palindromes

CF 1976D - Invertible Bracket Sequences

CF 1975F - Set

LeetCode 3864 - Minimum Cost to Partition a Binary String

LeetCode 3855 - Sum of K-Digit Numbers in a Range

LeetCode 3759 - Count Elements With at Least K Greater Values

LeetCode 3841 - Palindromic Path Queries in a Tree

LeetCode 3749 - Evaluate Valid Expressions

LeetCode 3826 - Minimum Partition Score

LeetCode 3739 - Count Subarrays With Majority Element II

LeetCode 3737 - Count Subarrays With Majority Element I

LeetCode 3721 - Longest Balanced Subarray II

LeetCode 3537 - Fill a Special Grid

LeetCode 3655 - XOR After Range Multiplication Queries II

LeetCode 3653 - XOR After Range Multiplication Queries I

LeetCode 3636 - Threshold Majority Queries

CF 459D - Pashmak and Parmida's problem

CF 452F - Permutation

Codeforces Round 274 (Div. 1)

CF 217C - Formurosa

CF 429D - Tricky Function

Codeforces Round 190 (Div. 1)

Codeforces Round 240 (Div. 1)

LeetCode 2426 - Number of Pairs Satisfying Inequality

Codeforces Round 124 (Div. 1)

LeetCode 2179 - Count Good Triplets in an Array

CF 413E - Maze 2D

CF 293E - Close Vertices

LeetCode 2343 - Query Kth Smallest Trimmed Number

CF 414C - Mashmokh and Reverse Operation

CF 150E - Freezing with Style

Codeforces Round 145 (Div. 2, ACM-ICPC Rules)

LeetCode 2407 - Longest Increasing Subsequence II

CF 196C - Paint Tree

Codeforces Round 199 (Div. 2)

CF 342E - Xenia and Tree

CF 232C - Doe Graphs

CF 234G - Practice

LeetCode 2792 - Count Nodes That Are Great Enough

LeetCode 1985 - Find the Kth Largest Integer in the Array

CF 161C - Abracadabra

LeetCode 3165 - Maximum Sum of Subsequence With Non-adjacent Elements

LeetCode 2519 - Count the Number of K-Big Indices

CF 321E - Ciel and Gondolas

Codeforces Round 134 (Div. 1)

LeetCode 3109 - Find the Index of Permutation

LeetCode 2613 - Beautiful Pairs

CF 321C - Ciel the Commander

CF 167D - Wizards and Roads

LeetCode 240 - Search a 2D Matrix II