Answer: RAZORPAY SDE-1 OA (2022) | Prefix Sum Optimization and Computational Geometry Ba

Q1: Approach Using brute force: Generate every subarray Calculate its sum Check if it lies in range Complexity: O(n²) Too slow for large inputs. Instead, use: Prefix Sum Balanced Search Structure (TreeMap/TreeSet concept) Binary Search Strategy Step 1 Compute running prefix sum. prefix[i] = sum of first i elements Step 2 For current prefix sum P: We need previous prefix sums X such that: lower <= P - X <= upper Rearranging: P - upper <= X <= P - ...