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