Problem Description
There is a given integer array. You need to find the minimum value within a specific range in this array.
Moreover, this range is dynamically provided and can be requested for multiple queries.
In other words, given specific indices i and j of the array,
you need to find the minimum value between i and j.
The goal of this course is to design and implement an efficient algorithm to solve this problem.
Problem Format
Input: An integer array nums and a list of queries queries.
– nums: An array of n integers (0 ≤ n ≤ 10^5, -10^9 ≤ nums[i] ≤ 10^9)
– queries: A list containing multiple pairs (i, j) (0 ≤ queries.length ≤ 10^5, 0 ≤ i ≤ j < n)
Output: Return a list of minimum values for each query.
Example Problems
Example 1
Input:
nums = [2, 0, 3, 5, 1]
queries = [[0, 2], [1, 4], [0, 4]]
Output:
[0, 1, 0]
Example 2
Input:
nums = [1, 2, 3, 4, 5]
queries = [[0, 0], [0, 4], [2, 3]]
Output:
[1, 1, 3]
Solution Strategy
There are several approaches to solving this problem.
The simplest way is to use linear search for each query.
However, this method has a worst-case time complexity of O(m * n),
so a more efficient method is required.
We will utilize data structures such as Segment Tree or Sparse Table
to find the minimum value for each query in O(log n) or O(1) time complexity.
Using Segment Tree
A Segment Tree is a data structure that efficiently handles range queries on a given array.
With this, we can build the Segment Tree in O(n) and process each query in O(log n).
Here is how to construct the Segment Tree and handle queries.
Segment Tree Implementation
// Segment Tree class
class SegmentTree {
private int[] tree;
private int n;
public SegmentTree(int[] nums) {
n = nums.length;
tree = new int[4 * n]; // Sufficiently sized tree array
build(nums, 0, 0, n - 1);
}
private void build(int[] nums, int node, int start, int end) {
if (start == end) {
tree[node] = nums[start]; // Store value at leaf node
} else {
int mid = (start + end) / 2;
build(nums, 2 * node + 1, start, mid);
build(nums, 2 * node + 2, mid + 1, end);
tree[node] = Math.min(tree[2 * node + 1], tree[2 * node + 2]);
}
}
public int query(int L, int R) {
return query(0, 0, n - 1, L, R);
}
private int query(int node, int start, int end, int L, int R) {
if (R < start || end < L) {
return Integer.MAX_VALUE; // Return infinity if not in range
}
if (L <= start && end <= R) {
return tree[node]; // Return node value if in range
}
int mid = (start + end) / 2;
int leftMin = query(2 * node + 1, start, mid, L, R);
int rightMin = query(2 * node + 2, mid + 1, end, L, R);
return Math.min(leftMin, rightMin); // Return minimum of both children
}
}
Final Implementation and Experiments
Now we will implement the main function that processes each query and returns the result.
By allowing users to request queries, we can efficiently retrieve the minimum value.
The final implementation is as follows.
public class MinValueFinder {
public int[] minInRange(int[] nums, int[][] queries) {
SegmentTree segmentTree = new SegmentTree(nums);
int[] results = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
results[i] = segmentTree.query(queries[i][0], queries[i][1]);
}
return results;
}
}
Time Complexity Analysis
– Segment Tree Construction: O(n)
– Each Query Processing: O(log n)
The overall time complexity is O(n + m * log n).
This is very efficient and can be sufficiently performed under restricted input conditions.
Conclusion
In this course, we solved the problem of finding the minimum value in a specific range of a given array using a Segment Tree.
The Segment Tree can efficiently handle multiple queries and is frequently used data structure in large datasets.
I hope this enhances your problem-solving abilities.