0% completed
Problem Statement
You are given an array nums
containing n
integers and a 2D array queries
of length q
, where queries[i] = [start<sub>i</sub>, end<sub>i</sub>], representing a starting and ending range (inclusive).
Return an array of size q
, where each element is the minimum
value in the respective range from nums
.
Examples
Example 1:
- Input: nums = [2, 6, 1, 12, 9, 5, 3, 7], queries = [[0, 3], [2, 5], [0, 1], [3, 7], [0, 7], [4, 6], [4, 5]]
- Output: [1, 1, 2, 3, 1, 3, 5]
- Justification:
- For the range
[0, 3]
, the minimum is1
. - For the range
[2, 5]
, the minimum is1
. - For the range
[0, 1]
, the minimum is2
. - For the range
[3, 7]
, the minimum is3
. - For the range
[0, 7]
, the minimum is1
. - For the range
[4, 6]
, the minimum is3
. - For the range
[4, 5]
, the minimum is5
.
- For the range
Example 2:
- Input: nums = [4, 8, 6, 2, 10, 15], queries = [[1, 3], [0, 2], [2, 4], [3, 5]]
- Output: [2, 4, 2, 2]
- Justification:
- For the range
[1, 3]
, the minimum is2
. - For the range
[0, 2]
, the minimum is4
. - For the range
[2, 4]
, the minimum is2
. - For the range
[3, 5]
, the minimum is2
.
- For the range
Example 3:
- Input: nums = [11, 13, 5, 8, 10, 12, 7, 14], queries = [[0, 4], [1, 3], [2, 5], [3, 6]]
- Output: [5, 5, 5, 7]
- Justification:
- For the range
[0, 4]
, the minimum is5
. - For the range
[1, 3]
, the minimum is5
. - For the range
[2, 5]
, the minimum is5
. - For the range
[3, 6]
, the minimum is7
.
- For the range
Constraints:
- 0 <= start<sub>i</sub> < end<sub>i</sub> <= 1000
Solution
To solve this problem, we will use a Segment Tree. A Segment Tree is a data structure that allows answering range queries in logarithmic time. The idea is to build a binary tree where each node represents a segment (or interval) of the array. The leaf nodes represent single elements, and the internal nodes store the minimum value of their respective children. This way, querying for the minimum value in any range can be done efficiently.
We will first construct the Segment Tree from the given array. This construction takes O(n) time. Once the tree is built, we can answer any range minimum query in O(log n) time. For each query, we will traverse the tree to find the minimum value in the specified range.
Step-by-Step Algorithm
Construct Segment Tree
-
Compute Height and Maximum Size:
- Step 1: Calculate the height of the segment tree using
ceil(log2(n))
. This gives the number of levels needed to cover all elements of the array. - Step 2: Calculate the maximum size of the segment tree array using
2 * (2^height) - 1
. This size ensures enough space for all nodes in the tree. - Step 3: Initialize the segment tree array with the calculated maximum size, typically filled with a 0 initially.
- Step 1: Calculate the height of the segment tree using
-
Build the Segment Tree:
- Step 1: Start the construction with the root node, which represents the entire range of the array
nums
, i.e., fromsegmentStart = 0
tosegmentEnd = n-1
. - Step 2: If the current segment represents a single element (i.e.,
segmentStart == segmentEnd
), store the value of that element in the current node of the segment tree. - Step 3: Recursively build the left and right subtrees.
- Step 3.1: Compute the middle index of the current segment using
mid = segmentStart + (segmentEnd - segmentStart) / 2
. - Step 3.2: Recursively build the left subtree with the range
[segmentStart, mid]
. - Step 3.3: Recursively build the right subtree with the range
[mid + 1, segmentEnd]
.
- Step 3.1: Compute the middle index of the current segment using
- Step 4: For internal nodes, store the minimum value of their left and right children. This is done by assigning
segmentTree[index] = Math.min(segmentTree[leftChildIndex], segmentTree[rightChildIndex])
.
- Step 1: Start the construction with the root node, which represents the entire range of the array
Query the Segment Tree
- Process Each Query:
- Step 1: For each query
[queryStart, queryEnd]
, start from the root node representing the range[0, n-1]
. - Step 2: Recursively check the overlap between the query range and the current segment:
- Step 2.1: If the query range fully covers the current segment, return the value stored in the current node.
- Step 2.2: If the query range lies completely outside the current segment, return a large value (e.g.,
Integer.MAX_VALUE
). - Step 2.3: If the query range partially overlaps with the current segment, recursively query the left and right children.
- Step 2.3.1: Compute the middle index of the current segment.
- Step 2.3.2: Recursively query the left subtree for the range
[segmentStart, mid]
. - Step 2.3.3: Recursively query the right subtree for the range
[mid + 1, segmentEnd]
.
- Step 3: Return the minimum of the values obtained from the left and right subtrees for the partially overlapping segments.
- Step 1: For each query
Algorithm Walkthrough
Let's consider the input [2, 6, 1, 12, 9, 5, 3, 7]
.
Construct Segment Tree
-
Initialization:
- Height Calculation: Given
n = 8
, the height of the segment tree isceil(log2(8)) = 3
. - Maximum Size Calculation: The maximum size of the segment tree is
2 * (2^3) - 1 = 15
. - Segment Tree Initialization: Initialize
segmentTree = new int[15]
with all values set toInteger.MAX_VALUE
.
- Height Calculation: Given
-
Building the Tree:
- Root Node (index 0, range [0, 7]):
- Compute Middle Index:
mid = 0 + (7 - 0) / 2 = 3
- Build Left Subtree (index 1, range [0, 3]):
- Compute Middle Index:
mid = 0 + (3 - 0) / 2 = 1
- Build Left Subtree (index 3, range [0, 1]):
- Compute Middle Index:
mid = 0 + (1 - 0) / 2 = 0
- Build Left Leaf Node (index 7, range [0, 0]):
- Store
segmentTree[7] = nums[0] = 2
- Store
- Build Right Leaf Node (index 8, range [1, 1]):
- Store
segmentTree[8] = nums[1] = 6
- Store
- Internal Node (index 3):
- Store
segmentTree[3] = Math.min(segmentTree[7], segmentTree[8]) = Math.min(2, 6) = 2
- Store
- Compute Middle Index:
- Build Right Subtree (index 4, range [2, 3]):
- Compute Middle Index:
mid = 2 + (3 - 2) / 2 = 2
- Build Left Leaf Node (index 9, range [2, 2]):
- Store
segmentTree[9] = nums[2] = 1
- Store
- Build Right Leaf Node (index 10, range [3, 3]):
- Store
segmentTree[10] = nums[3] = 12
- Store
- Internal Node (index 4):
- Store
segmentTree[4] = Math.min(segmentTree[9], segmentTree[10]) = Math.min(1, 12) = 1
- Store
- Compute Middle Index:
- Internal Node (index 1):
- Store
segmentTree[1] = Math.min(segmentTree[3], segmentTree[4]) = Math.min(2, 1) = 1
- Store
- Compute Middle Index:
- Build Right Subtree (index 2, range [4, 7]):
- Compute Middle Index:
mid = 4 + (7 - 4) / 2 = 5
- Build Left Subtree (index 5, range [4, 5]):
- Compute Middle Index:
mid = 4 + (5 - 4) / 2 = 4
- Build Left Leaf Node (index 11, range [4, 4]):
- Store
segmentTree[11] = nums[4] = 9
- Store
- Build Right Leaf Node (index 12, range [5, 5]):
- Store
segmentTree[12] = nums[5] = 5
- Store
- Internal Node (index 5):
- Store
segmentTree[5] = Math.min(segmentTree[11], segmentTree[12]) = Math.min(9, 5) = 5
- Store
- Compute Middle Index:
- Build Right Subtree (index 6, range [6, 7]):
- Compute Middle Index:
mid = 6 + (7 - 6) / 2 = 6
- Build Left Leaf Node (index 13, range [6, 6]):
- Store
segmentTree[13] = nums[6] = 3
- Store
- Build Right Leaf Node (index 14, range [7, 7]):
- Store
segmentTree[14] = nums[7] = 7
- Store
- Internal Node (index 6):
- Store
segmentTree[6] = Math.min(segmentTree[13], segmentTree[14]) = Math.min(3, 7) = 3
- Store
- Compute Middle Index:
- Internal Node (index 2):
- Store
segmentTree[2] = Math.min(segmentTree[5], segmentTree[6]) = Math.min(5, 3) = 3
- Store
- Compute Middle Index:
- Root Node (index 0):
- Store
segmentTree[0] = Math.min(segmentTree[1], segmentTree[2]) = Math.min(1, 3) = 1
The segment tree is `[1, 1, 3, 2, 1, 5, 3, 2, 6, 1, 12, 9, 5, 3, 7]
- Store
- Compute Middle Index:
- Root Node (index 0, range [0, 7]):
Query the Segment Tree
-
Query [0, 3]:
- Root Node (range [0, 7]):
- Query range [0, 3] partially overlaps, check left (range [0, 3]) and right (range [4, 7]) subtrees.
- Left Subtree (range [0, 3]):
- Query range fully overlaps, return
segmentTree[1] = 1
- Query range fully overlaps, return
- Result:
1
- Root Node (range [0, 7]):
-
Query [2, 5]:
- Root Node (range [0, 7]):
- Query range [2, 5] partially overlaps, check left (range [0, 3]) and right (range [4, 7]) subtrees.
- Left Subtree (range [0, 3]):
- Query range [2, 3] partially overlaps, check left (range [0, 1]) and right (range [2, 3]) subtrees.
- Right Subtree (range [2, 3]):
- Query range fully overlaps, return
segmentTree[4] = 1
- Query range fully overlaps, return
- Right Subtree (range [4, 7]):
- Query range [4, 5] partially overlaps, check left (range [4, 5]) subtree.
- Left Subtree (range [4, 5]):
- Query range fully overlaps, return
segmentTree[5] = 5
- Query range fully overlaps, return
- Return minimum of the results:
min(1,5) = 1
- Result:
1
- Root Node (range [0, 7]):
Code
Complexity Analysis
Time Complexity
-
Segment Tree Construction: O(n)
- Building the segment tree takes linear time because each node in the segment tree is visited once during construction.
-
Range Minimum Query: O(q*log n)
- Each query operation takes logarithmic time due to the height of the segment tree being log n. The query function traverses the tree's height, which is log n, visiting up to two branches at each level. For
q
queries, the total time complexity is the O(q*log n).
- Each query operation takes logarithmic time due to the height of the segment tree being log n. The query function traverses the tree's height, which is log n, visiting up to two branches at each level. For
-
Overall Time Complexity: O(n) + O(q log n)
- The overall time complexity is the sum of the time required to construct the segment tree and the time required to answer
q
range minimum queries.
- The overall time complexity is the sum of the time required to construct the segment tree and the time required to answer
Space Complexity
- Segment Tree Storage: O(n)
- The space required to store the segment tree is linear with respect to the number of elements in the input array
nums
. The segment tree array's size is approximately 2 * 2<sup>log n</sup> - 1, which simplifies to O(n).
- The space required to store the segment tree is linear with respect to the number of elements in the input array
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible