📂
Interview Prep
DSA Questions
DSA QuestionsLLD QuestionsInterview
DSA Questions
DSA QuestionsLLD QuestionsInterview
  • Introduction
  • Trees
    • Construct a binary tree from in-order and level order traversals
    • Next Greater Number BST
    • Balanced Binary Tree
    • Same Tree
    • Symmetric Tree
    • Inorder Traversal of Cartesian Tree
    • Convert Sorted Array to Binary Search Tree
    • Construct Binary Tree from Inorder and Postorder Traversal
    • Construct Binary Tree from Preorder and Inorder Traversal
    • Invert Binary Tree
    • Kth Smallest Element in a BST
    • Two Sum IV
    • Binary Search Tree Iterator
    • Recover Binary Search Tree
    • Binary Tree Inorder Traversal
    • Binary Tree Postorder Traversal
    • Binary Tree Preorder Traversal
    • Binary Tree Zigzag Level Order Traversal
    • Populating Next Right Pointers in Each Node
    • Populating Next Right Pointers in Each Node II
    • Path Sum
    • Path Sum II
    • Path Sum III
    • Sum Root to Leaf Numbers
    • Smallest String Starting From Leaf
    • Construct Binary Search Tree from Preorder Traversal
    • Construct BST from Postorder
    • Convert Level Order Traversal to BST
    • Maximum Depth of Binary Tree
    • Minimum Depth of Binary Tree
    • Binary Tree Level Order Traversal
    • Diagonal Traversal
    • Vertical Order Traversal of a Binary Tree
    • Binary Tree Right Side View
    • Left View of Binary Tree
    • Boundary Traversal of binary tree
    • Construct Binary Tree from Parent Array
    • Maximum Binary Tree II
    • Delete Leaves With a Given Value
    • Most Frequent Subtree Sum
    • Flatten Binary Tree to Linked List
    • Least Common Ancestor
    • Maximum width of a binary tree
    • Maximum Width of Binary Tree
    • Binary Tree Pruning
    • Find Bottom Left Tree Value
    • Maximum Product of Splitted Binary Tree
    • Recover a Tree From Preorder Traversal
    • Reverse alternate levels of a perfect binary tree
    • Find Largest Value in Each Tree Row
    • Shortest Unique Prefix
    • Implement Trie (Prefix Tree)
    • Foldable Binary Trees
    • Convert a given tree to its Sum Tree
    • Perfect Binary Tree Specific Level Order Traversal
    • Change a Binary Tree so that every node stores sum of all nodes in left subtree
    • Convert a given Binary Tree to Doubly Linked List
    • Binary Tree to a Circular Doubly Link List
    • Maximum edge removal from tree to make even forest
    • Print common nodes on path from root (or common ancestors)
    • Minimum Distance Between BST Nodes
    • Find distance between two nodes of a Binary Tree
    • Populate Inorder Successor for all nodes
    • Double Tree
    • Binary Tree Maximum Path Sum
    • Maximum Path Sum
    • Print all nodes at distance k from a given node
    • Binary Trees Custom Tree
    • Tilt of Binary Tree
    • Construct a special tree from given preorder traversal
    • Sum of k smallest elements in BST
    • Check whether BST contains Dead End or not
    • Binary Tree to Binary Search Tree Conversion
    • Remove nodes on root to leaf paths of length < K
    • Find Height of Binary Tree represented by Parent array
    • Vertical Sum in Binary Tree
    • Extract Leaves of a Binary Tree in a Doubly Linked List
    • Longest ZigZag Path in a Binary Tree
    • Validate Binary Search Tree
    • Maximum Level Sum of a Binary Tree
    • Convert Sorted List to Binary Search Tree
    • Merge Two Binary Trees
    • Diameter of Binary Tree
    • Count Good Nodes in Binary Tree
    • Serialize and Deserialize Binary Tree
    • Replace Words
    • Validate Binary Tree Nodes
    • Add One Row to Tree
    • Insufficient Nodes in Root to Leaf Paths
    • Pseudo-Palindromic Paths in a Binary Tree
    • Find Duplicate Subtrees
    • Inorder Successor in BST
    • Distribute Coins in Binary Tree
    • Delete Node in a BST
    • Count Complete Tree Nodes
    • Binary Tree Coloring Game
    • Delete Nodes And Return Forest
    • Sum of Nodes with Even-Valued Grandparent
    • Deepest Leaves Sum
    • Cousins in Binary Tree
    • Binary Search Tree to Greater Sum Tree
    • Stream of Characters
    • Closest Leaf in a Binary Tree
    • Binary Tree Cameras
    • Lowest Common Ancestor of a Binary Search Tree
    • Balance a Binary Search Tree
    • Maximum Sum BST in Binary Tree
    • Kth Ancestor of a Tree Node
    • Binary Tree Upside Down
    • Linked List in Binary Tree
    • LCA in a tree using Binary Lifting Technique
    • Number of Nodes in the Sub-Tree With the Same Label
    • Number of Good Leaf Nodes Pairs
  • Recursion & Backtracking
    • Knight's tour
    • Rat in a Maze
    • Valid Sudoku
    • Sudoku Solver
    • Remove Parenthesis
    • Subset
    • Subsets II
    • Permutations
    • Permutations II
    • Combinations
    • Combination Sum
    • Combination Sum II
    • Letter Combinations of a Phone Number
    • Generate Parentheses
    • Palindrome Partitioning
    • Gray Code
    • Permutation Sequence
    • N-Queens
    • N-Queens II
    • Remove Invalid Parentheses
    • Matchsticks to Square
    • Number of Atoms
  • Maths
    • Reaching Points
    • Fizz Buzz
    • Count Primes
    • Maximum 69 Number
    • All Factors
    • Greatest Common Divisor
    • Sorted Permutation Rank
    • Sorted Permutation Rank with Repeats
    • Trailing Zeros in Factorial
    • Rearrange Array
    • Power Of Two Integers
    • Game of Life
    • Reach a Number
    • Consecutive Numbers Sum
    • Simplified Fractions
    • Monotone Increasing Digits
    • Robot Bounded In Circle
    • Happy Number
    • Angle Between Hands of a Clock
    • Probability of a Two Boxes Having The Same Number of Distinct Balls
    • Best Meeting Point
    • Segmented Sieve (Print Primes in a Range)
    • Fibonacci Number
    • Optimal Division
    • Bulb Switcher
    • Digit multiplier
    • The kth Factor of n
  • Binary Searching & Sorting
    • Median of Two Sorted Arrays
    • Search in Rotated Sorted Array
    • Search in Rotated Sorted Array II
    • Matrix Median
    • Search Insert Position
    • Pow(x, n)
    • Rotated Array
    • Matrix Search
    • Find First and Last Position of Element in Sorted Array
    • Find square root of number upto given precision
    • Painter's Partition Problem
    • Allocate Books
    • Find Peak Element
    • Single Element in a Sorted Array
    • Capacity To Ship Packages Within D Days
    • Split Array Largest Sum
    • Koko Eating Bananas
    • Find the Smallest Divisor Given a Threshold
    • K-th Smallest Prime Fraction
    • Kth Smallest Element in a Sorted Matrix
    • Distribute Candies
    • Momos Market
    • Taj Mahal Entry
    • Sum of Mutated Array Closest to Target
    • First Bad Version
    • Random Pick with Weight
    • Search Suggestions System
    • Minimum Number of Days to Make m Bouquets
    • Aggressive cows
    • Chef Restaurant
    • Variation
    • Magnetic Force Between Two Balls
  • Strings
    • Number of Ways to Split a String
    • Valid Anagram
    • Palindrome String
    • Minimum Characters required to make a String Palindromic
    • Longest Common Prefix
    • Count And Say
    • Amazing Subarrays
    • Longest Palindromic Substring
    • Implement StrStr
    • Compare Version Numbers
    • Atoi
    • Valid Number
    • Valid Ip Addresses
    • Length of Last Word
    • Reverse the String
    • Roman to Integer
    • Integer To Roman
    • Add Binary Strings
    • Power of 2
    • Multiply Strings
    • Text Justification
    • ZigZag Conversion
    • Pretty Json
    • HTML Entity Parser
    • Find All Anagrams in a String
    • Check If a String Can Break Another String
    • Minimum Swaps to Make Strings Equal
    • Construct K Palindrome Strings
    • Print Words Vertically
    • First Unique Character in a String
    • Longest Word in Dictionary through Deleting
    • Check If a Word Occurs As a Prefix of Any Word in a Sentence
    • Maximum Number of Vowels in a Substring of Given Length
    • Reorganize String
    • Permutation in String
    • Long Pressed Name
    • Orderly Queue
    • Goat Latin
    • One Edit Distance
    • Is Subsequence
    • Reverse Vowels of a String
    • Valid Palindrome II
    • Check if two strings are k-anagrams or not
    • Permutation and Palindrome
    • Light Up the Bulbs
    • Number of Substrings With Only 1s
    • Last Substring in Lexicographical Order
    • Split Two Strings to Make Palindrome
  • BIT Manipulation
    • Single Number
    • Single Number II
    • Single Number III
    • Maximum XOR of Two Numbers in an Array
    • Divide Two Integers
    • Min XOR value
    • Number of 1 Bits
    • Reverse Bits
    • Different Bits Sum Pairwise
    • Count Triplets That Can Form Two Arrays of Equal XOR
    • Minimum Flips to Make a OR b Equal to c
    • XOR Queries of a Subarray
    • Sum of Two Integers
    • Bitwise ORs of Subarrays
    • Find a Value of a Mysterious Function Closest to Target
    • Find Kth Bit in Nth Binary String
  • Two Pointers
    • Merge Two Sorted Lists II
    • Intersection Of Sorted Arrays
    • Minimize the absolute difference
    • 3Sum Closest
    • 3 Sum Zero
    • Counting Triangles
    • Diffk
    • Remove Duplicates from Sorted Array
    • Remove Duplicates from Sorted Array II
    • Remove Element from Array
    • Sort by Color
    • Max Continuous Series of 1s
    • Container With Most Water
    • Check If All 1's Are at Least Length K Places Away
    • Push Dominoes
    • Maximum Width Ramp
    • Diagonal Traverse
    • Merge Sorted Array
    • Rotate Array
    • Form minimum number from given sequence
    • Interval List Intersections
    • Squares of a Sorted Array
    • Boats to Save People
  • Arrays
    • Move Zeroes
    • Trapping Rain Water
    • Longest Consecutive Sequence
    • K-Concatenation Maximum Sum
    • Find Pivot Index
    • Find a pair with the given difference
    • Chocolate Distribution Problem
    • Rotate a matrix by 90 degree without using any extra space
    • Spiral Order Matrix I
    • Min Steps in Infinite Grid
    • Add One To Number
    • Max Sum Contiguous Subarray
    • Maximum Absolute Difference
    • Repeat and Missing Number Array
    • MAXSPPROD
    • Minimum Number of Increments on Subarrays to Form a Target Array
    • Range Addition
    • Max Range Queries
    • Next Greater Element III
    • Murder
    • Interesting Sequences
    • Winning strategy
    • Palindromic Substrings
    • Array 3 Pointers
    • Flip
    • Max Non Negative SubArray
    • Spiral Order Matrix II
    • Pascal Triangle
    • Kth Row of Pascal's Triangle
    • Anti Diagonals
    • Triplets with Sum between given range
    • Noble Integer
    • Wave Array
    • Largest Number
    • Maximum Unsorted Subarray
    • Hotel Bookings Possible
    • Max Distance
    • Find Duplicate in Array
    • Maximum Consecutive Gap
    • Next Permutation
    • Find Permutation
    • Merge Intervals
    • Merge Overlapping Intervals
    • Set Matrix Zeros
    • First Missing Integer
    • N/3 Repeat Number
    • Queue Reconstruction by Height
    • Product of Array Except Self
    • Build an Array With Stack Operations
    • Search a 2D Matrix II
    • Wiggle Sort II
    • Shuffle an Array
    • Insert Delete GetRandom O(1)
    • Max Chunks To Make Sorted
    • Max Chunks To Make Sorted II
    • Global and Local Inversions
    • Number of Subarrays with Bounded Maximum
    • Arithmetic Slices
    • Maximum Sum of Two Non - Overlapping Subarrays
    • Car Pooling
    • Maximum Side Length of a Square with Sum Less than or Equal to Threshold
    • Remove Covered Intervals
    • Distant Barcodes
    • Summary Ranges
    • Queens That Can Attack the King
    • Rank Teams by Votes
    • Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
    • Maximum Product of Two Elements in an Array
    • Maximum Sum Circular Subarray
    • Range Addition
    • Max Range Queries
    • Shuffle the Array
    • The k Strongest Values in an Array
    • Most Profit Assigning Work
    • Friends Of Appropriate Ages
    • Missing Ranges
    • Max Consecutive Ones II
    • Max Consecutive Ones III
    • Minimum Domino Rotations For Equal Row
    • Partition Array into Disjoint Intervals
    • Maximize Distance to Closest Person
    • Car Fleet
    • Employee Free Time
    • Exam Room
    • Count Inversions in an array
    • Maximum sum of smallest and second smallest in an array
    • Number of Subsequences That Satisfy the Given Sum Condition
    • Longest Subarray of 1's After Deleting One Element
    • Count of Range Sum
    • Count of Smaller Numbers After Self
    • Range Sum Query - Mutable
    • Reverse Pairs
    • Last Moment Before All Ants Fall Out of a Plank
    • Minimum Difference Between Largest and Smallest Value in Three Moves
    • Find the Winner of an Array Game
  • Linked List
    • Intersection of Linked Lists
    • Reverse Linked List
    • Palindrome Linked List
    • Remove Duplicates from Sorted List
    • Remove Duplicates from Sorted List II
    • Merge Two Sorted Lists
    • Remove Nth Node From End of List
    • Rotate List
    • Reverse Linked List II
    • Reorder List
    • Linked List Cycle
    • Linked List Cycle II
    • Reverse Nodes in k-Group
    • Swap Nodes in Pairs
    • Add Two Numbers
    • Partition List
    • Insertion Sort List
    • Sort List
    • Flatten a Multilevel Doubly Linked List
    • Odd Even Linked List
    • Remove Zero Sum Consecutive Nodes from Linked List
    • Linked List Random Node
    • Design Browser History
    • LFU Cache
    • LRU Cache
  • Stacks & Queues
    • Generate all Parentheses
    • Reverse String
    • Simplify Path
    • Redundant Braces
    • Nearest Smaller Element
    • Largest Rectangle in Histogram
    • Evaluate Expression
    • Basic Calculator
    • Sliding Window Maximum
    • Min Stack
    • Daily Temperatures
    • Longest Valid Parentheses
    • Parsing A Boolean Expression
    • Minimum Cost Tree From Leaf Values
    • Decode String
    • Basic Calculator II
    • Next Greater Element II
    • Maximum Swap
    • Asteroid Collision
    • Sum of Subarray Minimums
    • Online Stock Span
    • Flatten Nested List Iterator
    • Score of Parentheses
    • Remove All Adjacent Duplicates in String II
    • Smallest Subsequence of Distinct Characters
    • Validate Stack Sequences
    • Reverse Substrings Between Each Pair of Parentheses
    • Dinner Plate Stacks
    • First negative integer in every window of size k
    • Method to Generate Binary Numbers from 1 to n
    • How to efficiently implement k stacks in a single array?
    • How to efficiently implement k Queues in a single array?
    • Hussain Set
  • HashMap & HashSet & Sliding Window
    • Make Sum Divisible by P
    • Largest Continuous Sequence Zero Sum
    • 2 Sum
    • 4 Sum
    • Diffk II
    • Group Anagrams
    • Copy List with Random Pointer
    • Equal
    • Longest Substring Without Repeating Characters
    • Find the longest substring with k unique characters in a given string
    • Longest Substring with At Most K Distinct Characters
    • Subarrays with K Different Integers
    • Number of Substrings Containing All Three Characters
    • Minimum Window Substring
    • Minimum Size Subarray Sum
    • Shortest Subarray with Sum at Least K
    • Fraction to Recurring Decimal
    • Max Points on a Line
    • Substring with Concatenation of All Words
    • Distinct Numbers in Window
    • 4Sum II
    • Hotel Reviews
    • Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
    • Top K Frequent Elements
    • Minimum Time to Collect All Apples in a Tree
    • Longest Substring with At Least K Repeating Characters
    • People Whose List of Favorite Companies Is Not a Subset of Another List
    • Rearrange Words in a Sentence
    • Longest Well-Performing Interval
    • Sort Characters By Frequency
    • Rabbits in Forest
    • Image Overlap
    • Brick Wall
    • Subarray Sums Divisible by K
    • Swap For Longest Repeated Character Substring
    • Short Encoding of Words
    • Find Duplicate File in System
    • Binary Subarrays With Sum
    • Contiguous Array
    • Subarrays with equal 1s and 0s
    • Equal 0, 1 and 2
    • Implement Magic Dictionary
    • Contains Duplicate III
    • Make Two Arrays Equal by Reversing Sub-arrays
    • Check If a String Contains All Binary Codes of Size K
    • Prison Cells After N Days
    • Find Elements in a Contaminated Binary Tree
    • Flip Columns For Maximum Number of Equal Rows
    • Least Number of Unique Integers after K Removals
    • Check Arithmetic Progression
    • X of a Kind in a Deck of Cards
    • Morning Assembly
    • Isomorphic Strings
    • Line Reflection
    • Grid Illumination
    • Maximum Frequency Stack
    • Length of the largest subarray with contiguous elements
    • Length of the largest subarray with contiguous elements
    • Find Two Non-overlapping Sub-arrays Each With Target Sum
    • Snapshot Array
    • Count pairs in array whose sum is divisible by K
    • Pairs of Non Coinciding Points
    • Find Anagram Mappings
    • Smallest subarray with all occurrences of a most frequent element
    • Insert Delete GetRandom O(1) - Duplicates allowed
    • Making File Names Unique
    • Avoid Flood in The City
    • Unique Word Abbreviation
    • Discrepancies in the Voters List
    • Check If Array Pairs Are Divisible by k
    • Max Value of Equation
    • Number of Sub-arrays With Odd Sum
    • Number of Good Ways to Split a String
    • Remove minimum elements from either side such that 2*min becomes more than max
  • Priority Queue
    • Heap Sort
    • Find K Pairs with Smallest Sums
    • Kth Largest Element in an Array
    • Merge k Sorted Lists
    • Median in a stream of integers
    • N max pair combinations
    • Magician and Chocolates
    • Find the Kth Smallest Sum of a Matrix With Sorted Rows
    • Kth Smallest Element in a Sorted Matrix
    • Smallest Range Covering Elements from K Lists
    • Top K Frequent Words
    • K Closest Points to Origin
    • Sort Integers by The Power Value
    • Minimum Number of Refueling Stops
    • IPO
    • Trapping Rain Water II
    • K-th Smallest Prime Fraction
    • Sliding Window Median
    • Range Sum of Sorted Subarray Sums
    • The Skyline Problem
  • Dynamic Programming
    • Stone Game V
    • Maximum Sum Increasing Subsequence
    • Minimum Path Sum
    • Grid Unique Paths
    • Unique Paths II
    • Climbing Stairs
    • Total number of different staircase that can made from N boxes
    • Number of Ways to Paint N × 3 Grid
    • Ways to color a 3xN Board
    • Unique Paths III
    • Decode Ways
    • Decode Ways II
    • Dungeon Game
    • Kingdom War
    • Coin Change
    • Triangle
    • Minimum Falling Path Sum
    • Minimum Falling Path Sum II
    • Minimum Score Triangulation of Polygon
    • Minimum Cost For Tickets
    • Best Time to Buy and Sell Stock
    • Best Time to Buy and Sell Stock II
    • Best Time to Buy and Sell Stock III
    • Best Time to Buy and Sell Stock IV
    • Best Time to Buy and Sell Stock with Cooldown
    • Best Time to Buy and Sell Stock with Transaction Fee
    • 2 Keys Keyboard
    • Perfect Squares
    • Longest Increasing Subsequence
    • Longest Bitonic Subsequence
    • Maximal Rectangle
    • Maximal Square
    • Maximum sum rectangle in a 2D matrix
    • Max Sum of Rectangle No Larger Than K
    • Coin Sum Infinite
    • House Robber
    • House Robber II
    • House Robber III
    • Jump Game
    • Jump Game II
    • Jump Game III
    • Integer Break
    • Edit Distance
    • Rod Cutting
    • Number of Submatrices That Sum to Target
    • Maximum Product Subarray
    • Subarray Product Less Than K
    • Arrange II
    • Longest Common Subsequence
    • Shortest Common Supersequence
    • Longest Repeating Subsequence
    • Distinct Subsequences
    • Distinct Subsequences II
    • Constrained Subsequence Sum
    • Max Sum Without Adjacent Elements
    • Maximum Points You Can Obtain from Cards
    • Largest area of rectangle with permutations
    • Regular Expression Matching
    • Unique Binary Search Trees
    • Unique Binary Search Trees II
    • Count Balanced Binary Trees of Height h
    • Word Break
    • Word Break II
    • Interleaving String
    • Longest Arithmetic Sequence
    • N digit numbers with digit sum S
    • Kth Manhattan Distance Neighbourhood
    • Wildcard Matching
    • Scramble String
    • Palindrome Partitioning II
    • Evaluate Expression To True
    • 0-1 Knapsack Problem
    • Subset Sum Problem
    • Last Stone Weight II
    • Target Sum
    • Ugly Number II
    • Matrix Block Sum
    • Count Square Submatrices with All Ones
    • Russian Doll Envelopes
    • Box Stacking Problem
    • Counting Bits
    • Longest Palindromic Subsequence
    • Count Different Palindromic Subsequences
    • Airplane Seat Assignment Probability
    • Tushar's Birthday Party
    • Flip Array
    • Intersecting Chords in a Circle
    • Stone Game
    • Numbers With Same Consecutive Differences
    • Super Ugly Number
    • LCS of three strings
    • Building Bridges
    • Partition Equal Subset Sum
    • Paint House
    • Paint House II
    • Paint House III
    • Burst Balloons
    • Minimum and Maximum values of an expression with * and +
    • Friends Pairing Problem
    • Partition to K Equal Sum Subsets
    • Maximum sum Bi-tonic Sub-sequence
    • Number of Longest Increasing Subsequence
    • Maximum Length of Pair Chain
    • Increasing Triplet Subsequence
    • Cutting a Rod
    • Maximum Product Cutting
    • Minimum insertions to form a palindrome
    • Optimal Binary Search Tree
    • Count number of ways to partition a set into k subsets
    • Egg Dropping Puzzle
    • Optimal Strategy for a Game
    • Mobile Numeric Keypad Problem
    • Find number of solutions of a linear equation of n variables
    • Count number of binary strings without consecutive 1’s
    • Non-negative Integers without Consecutive Ones
    • Ones and Zeroes
    • Probability of Knight to remain in the chessboard
    • Find if string is K-Palindrome or not
    • Shortest Uncommon Subsequence
    • Minimum Sum Path In 3-D Array
    • Longest Common Increasing Subsequence (LCS + LIS)
    • Perfect Sum Problem (Print all subsets with given sum)
    • Largest sum subarray with at-least k numbers
    • Program to find amount of water in a given glass
    • Number of Ways of Cutting a Pizza
    • Longest Increasing Path in a Matrix
    • Form Largest Integer With Digits That Add up to Target
    • Filling Bookcase Shelves
    • Minimum ASCII Delete Sum for Two Strings
    • Arithmetic Slices II - Subsequence
    • Beautiful Arrangement
    • Count All Valid Pickup and Delivery Options
    • Largest Sum of Averages
    • Equal Average Partition
    • Maximum Length of Repeated Subarray
    • Delete and Earn
    • Find Eventual Safe States
    • Length of Longest Fibonacci Subsequence
    • Max Dot Product of Two Subsequences
    • Number of Dice Rolls With Target Sum
    • Binary Trees With Factors
    • Predict the Winner
    • Can I Win
    • Delete Operation for Two Strings
    • Longest Arithmetic Subsequence of Given Difference
    • Cherry Pickup II
    • Out of Boundary Paths
    • Two City Scheduling
    • Uncrossed Lines
    • Number of Ways to Wear Different Hats to Each Other
    • Largest 1-Bordered Square
    • Largest Divisible Subset
    • Number of Music Playlists
    • Jump Game V
    • Longest repeating and non-overlapping substring
    • Number of Paths with Max Score
    • Coin Path
    • Frog Jump
    • Delete Columns to Make Sorted III
    • Equalize
    • Maximum sum alternating subsequence
    • Minimum number of increasing subsequences
    • Paint Fence
    • Count possible ways to construct buildings
    • Count Submatrices With All Ones
    • Cherry Pickup
    • Count of integers of length N and value less than K such that they contain digits only from the set
    • Stone Game IV
    • Number of subsequences of the form a^i b^j c^k
    • Highway Billboard Problem
    • Tiling with Dominoes
    • Unbounded Knapsack (Repetition of items allowed)
    • String Compression II
    • Get the Maximum Score
    • Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
    • Minimum Number of Days to Eat N Oranges
    • Odd Even Jump
  • Greedy
    • Minimum Numbers of Function Calls to Make Target Array
    • Bulbs
    • Majority Element
    • Highest Product
    • Assign Mice to Holes
    • Distribute Candy
    • Activity Selection Problem
    • Minimum Number of Arrows to Burst Balloons
    • Minimum Add to Make Parentheses Valid
    • Weighted Job Scheduling
    • Fractional Knapsack Problem
    • Seats
    • Gas Station
    • Group the People Given the Group Size They Belong To
    • Egyptian Fraction
    • Divide Array in Sets of K Consecutive Numbers
    • Minimum Cost to cut a board into squares
    • Maximize Sum Of Array After K Negations
    • Remove K Digits
    • Job Sequencing Problem
    • Maximum Length of Pair Chain
    • Maximum Number of Events That Can Be Attended
    • Partition Labels
    • Score After Flipping Matrix
    • Find smallest number with given number of digits and sum of digits
    • Reduce Array Size to The Half
    • Minimum sum of two numbers formed from digits of an array
    • Minimum sum of absolute difference of pairs of two arrays
    • Sum Of Fibonacci Numbers
    • Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
    • Largest Values From Labels
    • Video Stitching
    • Task Scheduler
    • Meeting Rooms II
    • Non-overlapping Intervals
    • Minimum Number of Platforms Required for a Railway/Bus Station
    • Save Energy
    • Difficult Economic Situation
    • Perimeter with conditions
    • Problem discussion
    • Winning Lottery
    • Maximum Number of Non-Overlapping Substrings
    • Minimum Swaps to Arrange a Binary Grid
  • Graphs, BFS & DFS
    • BFS
    • DFS
    • Find if there is a path between two vertices in a undirected graph
    • Clone Graph
    • Valid Path
    • Check if given undirected graph is connected or not
    • Connected Components in an undirected graph
    • Number of Islands
    • Surrounded Regions
    • Fox And Two Dots
    • 3 Cycle
    • Find the shortest path between two vertices in an undirected graph
    • Course Schedule
    • Word Search
    • MST
    • D-Dimensional MST
    • Dijkstra
    • Is Graph Bipartite?
    • Redundant Connection
    • Redundant Connection II
    • Word Ladder
    • Word Ladder II
    • As Far from Land as Possible
    • Commutable Islands
    • Count Servers that Communicate
    • Strongly Connected Components
    • Course Schedule II
    • Black Shapes
    • Word Search Board
    • Word Search II
    • Knight On Chess Board
    • Smallest Multiple With 0 and 1
    • Stepping Numbers
    • Number of Closed Islands
    • Minesweeper
    • Shortest Bridge
    • Friend Circles
    • Network Delay Time
    • Number of Enclaves
    • Most Stones Removed with Same Row or Column
    • Time Needed to Inform All Employees
    • Open the Lock
    • Critical Connections in a Network
    • Rotting Oranges
    • Accounts Merge
    • Possible Bipartition
    • Path with Maximum Gold
    • Reorder Routes to Make All Paths Lead to the City Zero
    • Course Schedule IV
    • Bus Routes
    • Minimum cost to connect cities
    • Cheapest Flights Within K Stops
    • Minimum Height Trees
    • Evaluate Division
    • Keys and Rooms
    • Find the Town Judge
    • Shortest Path with Alternating Colors
    • Check if There is a Valid Path in a Grid
    • Reconstruct Itinerary
    • Snakes and Ladders
    • Shortest Path in Binary Matrix
    • 01 Matrix
    • Pacific Atlantic Water Flow
    • Coloring A Border
    • Chef and Reversing
    • Optimize Water Distribution in a Village
    • Number of Operations to Make Network Connected
    • Mother Vertex
    • Number of Islands II
    • Number of Distinct Islands
    • Regions Cut By Slashes
    • Satisfiability of Equality Equations
    • Job Sequencing Problem (Using DSU)
    • Sentence Similarity II
    • Sort Items by Groups Respecting Dependencies
    • Eulerian path and circuit for undirected graph
    • Eulerian path and circuit for directed graph
    • Making A Large Island
    • Shortest Distance from All Buildings
    • Alphabet Board Path
    • Graph Valid Tree
    • Alien Dictionary
    • Similar String Groups
    • Walls and Gates
    • K-Similar Strings
    • Sliding Puzzle
    • Minimum number of swaps required to sort an array
    • Minimize Malware Spread
    • Articulation Points (or Cut Vertices) in a Graph
    • Doctor Strange
    • Castle RUN
    • Find the Maximum Flow
    • All Paths from Source Lead to Destination
    • Jump Game IV
    • Cut Off Trees for Golf Event
    • Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
    • Detect Cycles in 2D Grid
    • Find Latest Group of Size M
    • Minimum Number of Days to Disconnect Island
  • Geometry
    • Maximum Number of Darts Inside of a Circular Dartboard
    • Circle and Rectangle Overlapping
    • Island Perimeter
    • Maximum Number of Visible Points
  • Merge Sort
    • Question - 1
    • Question - 2
    • Question - 3
    • Question - 4
    • Question - 5
  • Segment Trees
    • Question - 1
    • Question - 2
    • Question - 3
    • Question - 4
    • Question - 5
    • Question - 6
    • Question - 7
    • Question - 8
    • Question - 9
  • Most consistent ways of dealing with the series of stock problems
Powered by GitBook
On this page

Segment Trees

PreviousQuestion - 5NextQuestion - 1

Last updated 2 months ago

A Segment Tree is a data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array. This includes finding the sum of consecutive array elements a[l…r], or finding the minimum element in a such a range in O(logn) time. Between answering such queries the Segment Tree allows modifying the array by replacing one element, or even change the elements of a whole subsegment (e.g. assigning all elements a[l…r] to any value, or adding a value to all element in the subsegment).

In general a Segment Tree is a very flexible data structure, and a huge number of problems can be solved with it. Additionally it is also possible to apply more complex operations and answer more complex queries (see ).

One important property of Segment Trees is, that they require only a linear amount of memory. The standard Segment Tree requires 4n vertices for working on an array of size n.

Query Results = O(logN), Updates = O(logN), Tree construction = O(N)

Left Child = 2*index, Right child = 2*index + 1

Advanced versions of Segment Trees