📂
Interview Prep
DSA Questions
DSA Questions
  • 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
  1. Segment Trees

Question - 3

Given an array of N positive integers. The task is to perform the following operations according to the type of query given. 1. Print the maximum pair product in a given range. [L-R] 2. Update Ai with some given value.

Examples:

Input: A={1, 3, 4, 2, 5} Queries: Type 1: L = 0, R = 2. Type 2: i = 1, val = 6 Type 1: L = 0, R = 2.

Output: 12 24

For the query1, the maximum product in a range [0, 2] is 3*4 = 12. For the query2, after an update, the array becomes [1, 6, 4, 2, 5] For the query3, the maximum product in a range [0, 2] is 6*4 = 24.

class Solution {
    static class Pair {
        int max, smax;

        Pair(int max, int smax) {
            this.max = max;
            this.smax = smax;
        }
    }

    public static void buildTree(int[] arr, Pair[] tree, int start, int end, int index) {
        if (start == end) {
            tree[index] = new Pair(arr[start], Integer.MIN_VALUE);
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(arr, tree, start, mid, 2 * index);
        buildTree(arr, tree, mid + 1, end, 2 * index + 1);
        tree[index] = new Pair(0, 0);
        tree[index].max = Math.max(tree[2 * index].max, tree[2 * index + 1].max);
        tree[index].smax = Math.min(Math.max(tree[2 * index].max, tree[2 * index + 1].smax),
                Math.max(tree[2 * index].smax, tree[2 * index + 1].max));
    }

    public static Pair findMaxProd(Pair[] tree, int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return new Pair(Integer.MIN_VALUE, Integer.MIN_VALUE);
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        Pair leftPair = findMaxProd(tree, start, mid, 2 * index, L, R);
        Pair rightPair = findMaxProd(tree, mid + 1, end, 2 * index + 1, L, R);
        Pair ans = new Pair(0, 0);
        ans.max = Math.max(leftPair.max, rightPair.max);
        ans.smax = Math.min(Math.max(leftPair.max, rightPair.smax), Math.max(leftPair.smax, rightPair.max));
        return ans;
    }

    public static void updateElement(int[] arr, Pair[] tree, int start, int end, int index, int updateIndex,
            int value) {
        if (start == end) {
            arr[start] = value;
            tree[index] = new Pair(value, Integer.MIN_VALUE);
            return;
        }
        int mid = start + (end - start) / 2;
        if (updateIndex > mid)
            updateElement(arr, tree, mid + 1, end, 2 * index + 1, updateIndex, value);
        else
            updateElement(arr, tree, start, mid, 2 * index, updateIndex, value);
        tree[index] = new Pair(0, 0);
        tree[index].max = Math.max(tree[2 * index].max, tree[2 * index + 1].max);
        tree[index].smax = Math.min(Math.max(tree[2 * index].max, tree[2 * index + 1].smax),
                Math.max(tree[2 * index].smax, tree[2 * index + 1].max));
    }

    public static void rangeQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        Pair tree[] = new Pair[4 * n];
        buildTree(arr, tree, 0, n - 1, 1);
        for (int[] query : queries) {
            if (query[0] == 1) {
                Pair product = findMaxProd(tree, 0, n - 1, 1, query[1], query[2]);
                System.out.println(product.max * product.smax);
            } else
                updateElement(arr, tree, 0, n - 1, 1, query[1], query[2]);
        }
    }
}
PreviousQuestion - 2NextQuestion - 4

Last updated 3 months ago