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) 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.
Contact Us