We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Queries with Fixed Length
  2. Discussions

Queries with Fixed Length

  • karlverdad
     + 0 comments

    Java 8

    Used a method where each value of the array -- starting from the maximum -- is used to mark all subarrays that overlap its index. Since we start from the maximum, all subsequent values won't overwrite the marks.

    Preliminary function setup (i.e. sorting, query for loop):

        // Struct { array value, index in the array }
    public static class IndexTracker {
        public int value;
        public int index;
        
        public IndexTracker(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
    
    // Helps sort the list in descending order
    public static class IndexTrackerComparator implements Comparator<IndexTracker> {
        @Override
        public int compare(IndexTracker trackerA, IndexTracker trackerB) {
            return Integer.compare(trackerB.value, trackerA.value);
        }
    }

    public static List<Integer> solve(List<Integer> arr, List<Integer> queries) { 
	// Get reverse sorted list of struct {value: arr[i], index: i} 
        List<IndexTracker> trackers = new ArrayList<>();
        for (int i = 0; i < arr.size(); i++) {
            IndexTracker tracker = new IndexTracker(arr.get(i), i);
            trackers.add(tracker);
        }
        Collections.sort(trackers, new IndexTrackerComparator());
        
        // Loop through each query
        List<Integer> minima = new ArrayList<>();
        for (int query : queries) {
            minima.add(minOfMaxSubarray(trackers, arr.size(), query));
        }
        
        return minima;
    }

    Actual function logic:

        public static int minOfMaxSubarray(List<IndexTracker> sortedTrackers, int arraySize, int length) {
        // Create a list of subarray max values
        List<Integer> marks = new ArrayList<>();
        for (int i = 0; i < arraySize - (length - 1); i++) {
            marks.add(-1);      // -1 indicates unmarked
        }
        int markedCount = 0;
        
        // Loop through each index starting from the maximum
        for (IndexTracker tracker : sortedTrackers) {
            // Range of subarrays that overlap the current index
            int left = tracker.index - (length - 1);
            int right = tracker.index;

            // Marks affected subarrays with the value at the current index
            for (int i = left; i <= right; i++) {
                if (i < 0 || i >= marks.size()) {
                    continue;
                }
                if (marks.get(i) == -1) {
                    marks.set(i, tracker.value);
                    markedCount++;
                }
            }
            
            // Once all subarrays have been marked, returns the most recently used value (equivalent to the minimum)
            if (markedCount >= marks.size()) {
                return tracker.value;
            }    
        }
        
        return -1;      // Error return
    }