Range Minimum Query (RMQ) in Python
Range Minimum Query (RMQ) problem involves finding the minimum value within a specified range of a given array. This problem is used in various fields such as computer science, data structures, and algorithms, with various applications.
Examples:
Input: arr = [5, 2, 7, 1, 9, 4, 3], Q = [1, 4]
Output: 1
Explanation: The minimum value within the range [1, 4] is 1, located at index 3.Input: arr = [10, 3, 8, 6, 12, 5], Q = [2, 5]
Output: 12
Explanation: The minimum value within the range [2, 5] is 4, located at index 3.
Range Minimum Query (RMQ) using Brute Force Approach in Python:
- Iterate through each element within the given range and find the minimum.
- Iterate through the elements within the given range.
- Keep track of the minimum element found so far.
- Return the minimum element.
Below is the implementation of the above approach:
# Function to find the minimum element using Brute Force
def brute_force_rmq(arr, start, end):
result = arr[start]
for i in range(start + 1, end + 1):
result = min(result, arr[i])
return result
# Example usage:
arr = [5, 2, 7, 1, 9, 4, 3]
start, end = 1, 4
print("Minimum within the range [1, 4]:", brute_force_rmq(arr, start, end))
Output
Minimum within the range [1, 4]: 1
Time Complexity: O(n) for each query, where n is the size of the array.
Auxiliary Space: O(1).
Range Minimum Query (RMQ) using Segment Tree in Python:
- Build a segment tree data structure to efficiently answer range queries.
- Construct a segment tree from the given array.
- Query the segment tree for the minimum within the specified range.
- For each query, start from the root node (index 0) and check for the following cases:
- If the query range lies outside the range of the node, then return INT_MAX in case of Min Quer.
- Else If the query range lies completely inside the range of node, then return the value at node.
- Else call the query on both the left and right s
Below is the implementation of the above approach:
class SegmentTree:
def __init__(self, arr):
self.arr = arr
self.tree = [None] * (4 * len(arr))
self.build(0, 0, len(arr) - 1)
# function to build the segment tree
def build(self, node, start, end):
if start == end:
self.tree[node] = self.arr[start]
else:
mid = (start + end) // 2
self.build(2 * node + 1, start, mid)
self.build(2 * node + 2, mid + 1, end)
self.tree[node] = min(self.tree[2 * node + 1],
self.tree[2 * node + 2])
# function to find the minimum from start to end
def query(self, node, start, end, left, right):
if right < start or left > end:
return float('inf')
if left <= start and right >= end:
return self.tree[node]
mid = (start + end) // 2
return min(self.query(2 * node + 1, start, mid, left, right),
self.query(2 * node + 2, mid + 1, end, left, right))
# Example usage:
arr = [5, 2, 7, 1, 9, 4, 3]
segment_tree = SegmentTree(arr)
start, end = 1, 4
print("Minimum within the range [1, 4]:", segment_tree.query(
0, 0, len(arr) - 1, start, end))
Output
Minimum within the range [1, 4]: 1
Time Complexity:
- Construction: O(n)
- Query: O(logn)
Auxiliary Space: O(n) for the segment tree
Contact Us