Segment Tree Interview Questions

Array Binary Search Design Segment Tree Ordered Set

Rank

#3181HardFrequency: 69.8%

Find Building Where Alice and Bob Can Meet

Array Binary Search Stack Binary Indexed Tree Segment Tree Heap (Priority Queue)Monotonic Stack

Rank

#3435HardFrequency: 68.4%

Block Placement Queries

Array Binary Search Binary Indexed Tree Segment Tree Ordered Set

Rank

#4215HardFrequency: 67.6%

Good Subsequence Queries

Array Math Segment Tree Number Theory

Rank

#3423HardFrequency: 62.5%

Maximum Sum of Subsequence With Non-adjacent Elements

Array Divide and Conquer Dynamic Programming Segment Tree

Rank

#880HardFrequency: 59.8%

Rectangle Area II

Asked at Flipkart

Array Segment Tree Sweep Line Ordered Set

Rank

#2357HardFrequency: 56.3%

Count Integers in Intervals

Asked at LinkedIn

Design Segment Tree Ordered Set

Rank

#3436HardFrequency: 55.1%

Find Subarray With Bitwise OR Closest to K

Asked at Salesforce

Array Binary Search Bit Manipulation Segment Tree

Rank

#3789HardFrequency: 55%

Maximize Subarrays After Removing One Conflicting Pair

Asked at LinkedIn

Array Segment Tree Enumeration Prefix Sum

Rank

#699HardFrequency: 47.5%

Falling Squares

Array Segment Tree Ordered Set

#10

Rank

#493HardFrequency: 44.6%

Reverse Pairs

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Treap

#11

Rank

#715HardFrequency: 42.7%

Range Module

Design Segment Tree Ordered Set

#12

Rank

#218HardFrequency: 37.9%

The Skyline Problem

Array Divide and Conquer Binary Indexed Tree Segment Tree Sweep Line Sorting Heap (Priority Queue)Ordered Set

#13

Rank

#315HardFrequency: 33.1%

Count of Smaller Numbers After Self

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Treap

#14

Rank

#327HardFrequency: 31.3%

Count of Range Sum

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Treap

#15

Rank

#731MediumFrequency: 29.5%

My Calendar II

Asked at Apple

Array Binary Search Design Segment Tree Prefix Sum Ordered Set

#16

Rank

#406MediumFrequency: 28.1%

Queue Reconstruction by Height

Array Binary Indexed Tree Segment Tree Sorting

#17

Rank

#2526HardFrequency: 25.4%

Longest Increasing Subsequence II

Array Divide and Conquer Dynamic Programming Binary Indexed Tree Segment Tree Queue Monotonic Queue

#18

Rank

#673MediumFrequency: 25.1%

Number of Longest Increasing Subsequence

Asked at Meta

Array Dynamic Programming Binary Indexed Tree Segment Tree Longest Increasing Subsequence

#19

Rank

#3674HardFrequency: 24.4%

Count Non-Decreasing Subarrays After K Operations

Array Stack Segment Tree Queue Sliding Window Monotonic Stack Monotonic Queue

#20

Rank

#3920HardFrequency: 23.6%

Minimum Stability Factor of Array

Array Math Binary Search Greedy Segment Tree Number Theory

#21

Rank

#308MediumFrequency: 23.3%

Range Sum Query 2D - Mutable

Array Design Binary Indexed Tree Segment Tree Matrix Sqrt Decomposition

#22

Rank

#3790EasyFrequency: 22.1%

Fruits Into Baskets II

Array Binary Search Segment Tree Simulation Ordered Set

#23

Rank

#4047HardFrequency: 22.1%

Longest Balanced Subarray II

Array Hash Table Divide and Conquer Segment Tree Prefix Sum

#24

Rank

#3681MediumFrequency: 20.9%

Maximum Area Rectangle With Point Constraints I

Array Math Binary Indexed Tree Segment Tree Geometry Sorting Enumeration

#25

Rank

#3775HardFrequency: 20.9%

Separate Squares II

Array Binary Search Segment Tree Sweep Line

#26

Rank

#2297HardFrequency: 20.3%

Amount of New Area Painted Each Day

Array Segment Tree Ordered Set

#27

Rank

#1511MediumFrequency: 20%

Count Number of Teams

Array Dynamic Programming Binary Indexed Tree Segment Tree

#28

Rank

#2658HardFrequency: 20%

Count the Number of K-Big Indices

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

#29

Rank

#3139HardFrequency: 20%

Subarrays Distinct Element Sum of Squares II

Array Hash Table Binary Indexed Tree Segment Tree

#30

Rank

#3184HardFrequency: 20%

Maximum Balanced Subsequence Sum

Array Binary Search Dynamic Programming Binary Indexed Tree Segment Tree

#31

Rank

#732HardFrequency: 19.5%

My Calendar III

Binary Search Design Segment Tree Prefix Sum Ordered Set

#32

Rank

#2512MediumFrequency: 19.5%

Longest Uploaded Prefix

Hash Table Binary Search Union-Find Design Binary Indexed Tree Segment Tree Heap (Priority Queue)Ordered Set

#33

Rank

#4074MediumFrequency: 19.5%

Count Subarrays With Majority Element I

Array Hash Table Divide and Conquer Segment Tree Merge Sort Counting Prefix Sum

#34

Rank

#683HardFrequency: 18%

K Empty Slots

Array Binary Indexed Tree Segment Tree Queue Sliding Window Heap (Priority Queue)Ordered Set Monotonic Queue

#35

Rank

#1728HardFrequency: 18%

Fancy Sequence

Math Design Segment Tree Number Theory Fermat's Little Theorem

#36

Rank

#2513HardFrequency: 18%

Number of Pairs Satisfying Inequality

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

#37

Rank

#510MediumFrequency: 16.4%

Count Subarrays With More Ones Than Zeros

Array Hash Table Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

#38

Rank

#2380HardFrequency: 16.4%

Booking Concert Tickets in Groups

Binary Search Design Binary Indexed Tree Segment Tree

#39

Rank

#3364HardFrequency: 16.4%

Minimum Sum of Values by Dividing Array

Array Binary Search Dynamic Programming Bit Manipulation Segment Tree Queue

#40

Rank

#3970MediumFrequency: 16.4%

Power Update After K-th Largest Insertion I

Array Hash Table Math Segment Tree Sorting Heap (Priority Queue)

#41

Rank

#3791MediumFrequency: 14.6%

Fruits Into Baskets III

Array Binary Search Segment Tree Ordered Set

#42

Rank

#4045MediumFrequency: 13.2%

Longest Balanced Subarray I

Array Hash Table Divide and Conquer Segment Tree Prefix Sum

#43

Rank

#2319HardFrequency: 12%

Longest Substring of One Repeating Character

Array String Segment Tree Ordered Set

#44

Rank

#307MediumFrequency: 10.5%

Range Sum Query - Mutable

Array Divide and Conquer Design Binary Indexed Tree Segment Tree Sqrt Decomposition

#45

Rank

#3688HardFrequency: 10.5%

Maximize Subarray Sum After Removing All Occurrences of One Element

Array Hash Table Divide and Conquer Dynamic Programming Segment Tree Prefix Sum

#46

Rank

#2280HardFrequency: 10.5%

Count Good Triplets in an Array

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

#47

Rank

#3804HardFrequency: 10.5%

Maximize Active Section with Trade II

Array String Binary Search Segment Tree

#48

Rank

#4007HardFrequency: 7.3%

Maximum Total Subarray Value II

Array Greedy Segment Tree Heap (Priority Queue)

#49

Rank

#1294MediumFrequency: 7.3%

Range Frequency Queries

Array Hash Table Binary Search Design Segment Tree

#50

Rank

#4075HardFrequency: 7.3%

Count Subarrays With Majority Element II

Array Hash Table Divide and Conquer Segment Tree Merge Sort Prefix Sum

#51

Rank

#3689HardFrequency: 5.5%

Maximum Area Rectangle With Point Constraints II

Array Math Binary Indexed Tree Segment Tree Geometry Sorting

#52

Rank

#2765HardFrequency: 5%

Make Array Empty

Array Binary Search Greedy Binary Indexed Tree Segment Tree Sorting Ordered Set

#53

Rank

#3878HardFrequency: 5%

Maximize Count of Distinct Primes After Split

Array Hash Table Math Segment Tree Number Theory Ordered Set

#54

Rank

#3163EasyFrequency: 5%

Subarrays Distinct Element Sum of Squares I