Day 78 of 100 days dsa coding challenge

Source: Dev.to

Introduction

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem‑solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

#100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem Statement

You are given a sorted array arr[] and a 2D array queries[][], where queries[i] represents a query in the form [l, r, x].
For each query, count how many times the number x appears in the subarray arr[l...r](source).

Examples

Example 1

Input

arr[] = [1, 2, 2, 4, 5, 5, 5, 8]
queries[][] = [[0, 7, 5], [1, 2, 2], [0, 3, 7]]

Output

[3, 2, 0]

Explanation

• Query [0, 7, 5] → subarray [1, 2, 2, 4, 5, 5, 5, 8]; 5 occurs 3 times.
• Query [1, 2, 2] → subarray [2, 2]; 2 occurs 2 times.
• Query [0, 3, 7] → subarray [1, 2, 2, 4]; 7 is not present.

Example 2

Input

arr[] = [1, 3, 3, 3, 6, 7, 8]
queries[][] = [[0, 3, 3], [4, 6, 3], [1, 5, 6]]

Output

[3, 0, 1]

Explanation

• Query [0, 3, 3] → subarray [1, 3, 3, 3]; 3 appears 3 times.
• Query [4, 6, 3] → subarray [6, 7, 8]; 3 not found.
• Query [1, 5, 6] → subarray [3, 3, 3, 6, 7]; 6 occurs 1 time.

Constraints

• 1 ≤ arr.size(), queries.size() ≤ 10⁵
• 1 ≤ arr[i], x ≤ 10⁶
• 0 ≤ l ≤ r < arr.size()

Solution

from bisect import bisect_left, bisect_right

class Solution:
    def countXInRange(self, arr, queries):
        """
        Returns a list where each element corresponds to the count of x in the
        subarray arr[l...r] for each query [l, r, x].
        """
        res = []
        for l, r, x in queries:
            left = bisect_left(arr, x, l, r + 1)
            right = bisect_right(arr, x, l, r + 1)
            res.append(right - left)
        return res