093 — Upper Bound

092-এ "প্রথম ≥ x" খুঁজলে। এই note তার যমজ ভাই: "প্রথম > x" — upper bound, Python-এর bisect_right। পার্থক্যটা এত ছোট (শর্তে শুধু একটা =-এর ছোঁয়া) যে অনেকে গুলিয়ে ফেলে — আর সেই গুলিয়ে ফেলা নিঃশব্দে wrong answer দেয়। কিন্তু দুটো পাশাপাশি বুঝলে একটা দারুণ ক্ষমতা পাবে: "x আছে ঠিক কয়বার?" এক বিয়োগেই বলা। ধীরে পড়ো, 092-টা পাশে খুলে রাখো।

Source

• Original source: Classic exercise (Python-এর bisect.bisect_right-এর হাতে-বানানো রূপ)
• Platform: — (standard library concept; related: Python docs — https://docs.python.org/3/library/bisect.html)
• Topic: Math-based programming fundamentals → Level 7: Binary Search on Answer
• Difficulty: Easy
• Pattern: first > x (প্রথম যেখানে a[i] > x)
• Basic idea inherited from: 092 — Lower Bound

1. Problem in simple words

একটা sorted array a আর একটা সংখ্যা x। বলতে হবে — সবচেয়ে ছোট index i যেখানে a[i] > x (কড়াকড়ি বড়, সমান না)। অর্থাৎ x-এর সব occurrence পেরিয়ে ঠিক পরের জায়গা।

আরেকভাবে: x-কে array-তে ঢোকালে, ডান দিক ঘেঁষে (একই মানের সবার পরে) সে কোন index-এ বসবে — সেটাই upper bound।

092-এর সাথে পার্থক্য: lower bound x-এর প্রথম সমান-বা-বড়ে আঙুল রাখে; upper bound x-এর সব সমান পেরিয়ে প্রথম কড়া-বড়ে। x না থাকলে দুটো একই উত্তর দেয়।

2. What is the math idea?

আবার সেই monotonic শর্তে binary search — শুধু শর্তটা এবার a[i] > x। এটাও একবার সত্যি হলে ডান দিকে সব সত্যি, তাই সিঁড়ি F F F T T T, আর প্রথম T-টাই উত্তর।

বড় idea: lower bound (>= x) আর upper bound (> x)-এর ফারাকটাই বলে দেয় x array-তে কয়বার আছে — কারণ মাঝের সব index-এর element ঠিক x।

3. Which basic idea does this inherit from?

092 (Lower Bound)-এর কাঠামো এখানে হুবহু — while lo < hi, hi = mid, lo = mid + 1, hi = len(a) দিয়ে শুরু। একটাই লাইন বদলায়:

• 092: if a[mid] < x (শর্ত >= x-এর জন্য)
• 093: if a[mid] <= x (শর্ত > x-এর জন্য)

ব্যস, ওই একটা = যোগ হওয়াই lower bound-কে upper bound বানিয়ে দেয়। এত কাছাকাছি বলেই দুটো একসাথে শেখা উচিত — তাহলে আর গুলোবে না।

4. Real-life analogy

আবার লাইব্রেরির সেই sorted তাক, একই number x-এর কয়েকটা বই পাশাপাশি রাখা। 092-তে নতুন বই বসাতাম এই দলটার ঠিক আগে (বাঁয়ে)।

এবার তুমি বসাও দলটার ঠিক পরে (ডানে) — সব x পেরিয়ে। যদি x-এর কোনো বই না থাকে, "আগে" আর "পরে" একই জায়গা — তখন lower আর upper bound মিলে যায়। কিন্তু x-এর তিনটা বই থাকলে দুটোর মাঝে ঠিক তিন ঘরের ফাঁক — সেই ফাঁকই গুনে বলে দেয় কয়টা x আছে।

5. Visual explanation

a = [1, 3, 3, 3, 7], x = 3। শর্ত এবার "a[i] > 3?":

a     =  [ 1   3   3   3   7 ]
index =    0   1   2   3   4     5 (শেষের পরে)
a[i]>3  =  F   F   F   F   T
                            ↑
        প্রথম T → upper bound = 4

lower bound (092, প্রথম ≥3) = 1
upper bound (এখানে, প্রথম >3) = 4
ফারাক = 4 - 1 = 3  →  3 আছে ঠিক 3 বার!

দুটো bound-এর মাঝের সব ঘরে (index 1, 2, 3) বসে আছে ঠিক x = 3। তাই ফারাক = গণনা।

6. Example input and output

a (sorted)            x   ->  upper bound   (ব্যাখ্যা)
-----------------------------------------------------
[1, 3, 3, 3, 7]       3   ->  4     (সব 3 পেরিয়ে, 7-এর index)
[1, 3, 3, 3, 7]       4   ->  4     (4 নেই; lower==upper)
[1, 3, 3, 3, 7]       7   ->  5     (সব 7 পেরিয়ে = len)
[1, 3, 3, 3, 7]       0   ->  0     (সবার চেয়ে ছোট; শুরুতে)
[1, 3, 3, 3, 7]       8   ->  5     (সবার চেয়ে বড় = len)
[]                    5   ->  0     (খালি array)

খেয়াল করো: x = 7 (সবচেয়ে বড় element)-এ upper bound = 5 = len(a), কারণ 7-এর চেয়ে কড়া-বড় কিছুই নেই — সব পেরিয়ে শেষের পরে।

7. Brute force thinking

বাঁ থেকে এক এক করে দেখো, প্রথম যেখানে a[i] > x পেলে সেই index:

def upper_bound_brute(a, x):
    for i in range(len(a)):
        if a[i] > x:
            return i
    return len(a)            # কেউ > x না — শেষের পরে

092-এর brute force-এর সাথে একটাই পার্থক্য: শর্তে >= নয়, >। বাকি সব এক — return len(a) লাইনটাও একই কারণে দরকার (x সবার চেয়ে বড়/সমান হলে)।

8. Why brute force may be slow

সেই একই কথা — সবচেয়ে খারাপ ক্ষেত্রে পুরো array, O(n)। sorted তথ্য কাজে লাগে না।

n = 1,000,000 হলে:
  linear scan   : ~1,000,000 তুলনা  (O(n))
  binary search : ~20 তুলনা          (O(log n))

আর "x কয়বার আছে" বের করতে যদি lower + upper দুটোই linear-এ করো, সেটা O(n) — অথচ দুটো binary search মিলে O(log n)।

9. Better thinking

শর্ত a[i] > x-এর সিঁড়ি F F F T T T — monotonic। প্রথম T খুঁজি binary search-এ, ঠিক 092-এর মতো, শুধু তুলনায় <=:

def upper_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1        # mid এখনো F (a[mid] ≤ x) — বাঁ অর্ধেক বাদ
        else:
            hi = mid            # mid হয়তো প্রথম T (a[mid] > x) — রেখে দাও
    return lo

প্রতি ধাপে অর্ধেক → O(log n)।

10. Thinking tweak

আসল মোচড়: < কে <= বানালেই lower bound হয়ে যায় upper bound। কারণ a[mid] == x ক্ষেত্রটা কোন দিকে যায়, সেটাই ঠিক করে আমরা x-এর বাঁয়ে থামছি না ডানে।

• 092-এ a[mid] == x হলে শর্ত (< x) মিথ্যা → hi = mid → x-এর দিকে চেপে থামি → বাঁ bound।
• 093-এ a[mid] == x হলে শর্ত (<= x) সত্যি → lo = mid + 1 → x পেরিয়ে যাই → ডান bound।

এই এক অক্ষরের (=) পার্থক্যেই duplicate-এ দুই দিকের সীমানা। আর upper - lower = count — এই সম্পর্কটা মনে গেঁথে নাও, গোনা-জাতীয় বহু problem-এ লাগবে (102-এও এর আত্মীয়)।

11. Step-by-step dry run

a = [1, 3, 3, 3, 7], x = 3 চালাই (hi = 5):

step	lo	hi	mid	a[mid]	a[mid] <= 3?	সিদ্ধান্ত
1	0	5	2	3	হ্যাঁ	lo = mid + 1 = 3
2	3	5	4	7	না	hi = mid = 4
3	3	4	3	3	হ্যাঁ	lo = mid + 1 = 4
—	4	4	—	—	—	lo == hi → return 4

উত্তর 4 — সব 3 পেরিয়ে 7-এর index। তুলনা করো 092-এর dry run-এর সাথে (একই array, একই x, কিন্তু উত্তর 1) — পুরো পার্থক্যটা ওই < বনাম <=।

12. Python solution

def upper_bound(a, x):
    """sorted a-তে প্রথম index যেখানে a[i] > x; কেউ না থাকলে len(a)।"""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1            # mid এখনো ≤ x — বাঁ অর্ধেক বাদ
        else:
            hi = mid                # mid > x, হয়তো প্রথম T — রেখে দাও
    return lo


def lower_bound(a, x):              # 092 থেকে, count বের করতে লাগবে
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def count_of(a, x):
    """x array-তে কয়বার আছে = upper - lower।"""
    return upper_bound(a, x) - lower_bound(a, x)


from bisect import bisect_right


def upper_bound_brute(a, x):
    for i in range(len(a)):
        if a[i] > x:
            return i
    return len(a)


# --- ছোট test গুলো (সব pass করা উচিত) ---
a = [1, 3, 3, 3, 7]
assert upper_bound(a, 3) == 4            # সব 3 পেরিয়ে
assert upper_bound(a, 4) == 4            # 4 নেই
assert upper_bound(a, 7) == 5            # সব 7 পেরিয়ে = len
assert upper_bound(a, 0) == 0            # সবচেয়ে ছোট
assert upper_bound(a, 8) == 5            # সবচেয়ে বড় = len
assert upper_bound([], 5) == 0           # খালি array

# upper - lower = count যাচাই
assert count_of(a, 3) == 3               # 3 আছে 3 বার
assert count_of(a, 7) == 1               # 7 আছে 1 বার
assert count_of(a, 4) == 0               # 4 নেই

# bisect_right আর brute force-এর সাথে মিলিয়ে দেখি
big = [0, 2, 2, 4, 4, 4, 6, 9, 9, 10]
for x in range(-2, 13):
    assert upper_bound(big, x) == bisect_right(big, x)
    assert upper_bound(big, x) == upper_bound_brute(big, x)

print(upper_bound(a, 3))   # 4
print(count_of(a, 3))      # 3
print(upper_bound(a, 7))   # 5
print("সব test pass!")

13. Line-by-line explanation

lo, hi = 0, len(a)

092-এর মতোই range [0, len(a)] — কারণ উত্তর len(a)-ও হতে পারে (x সবার চেয়ে বড় হলে)।

if a[mid] <= x: lo = mid + 1

এটাই একমাত্র পার্থক্য 092-এর সাথে। a[mid] <= x মানে mid এখনো শর্ত (> x) পূরণ করে না — তাই mid সহ বাঁ অর্ধেক বাদ। লক্ষ করো a[mid] == x ক্ষেত্রটাও এখানে পড়ে, তাই x-এর সমান ঘরগুলো পেরিয়ে যাই (ডান bound)।

else: hi = mid

a[mid] > x — mid নিজেই হয়তো প্রথম T। রেখে দিই।

return upper_bound(a, x) - lower_bound(a, x)

count_of-এর হৃদয়: দুই bound-এর ফারাকই x-এর গণনা — মাঝের সব ঘরে ঠিক x বসে আছে।

cross-check-এ bisect_right আর brute force দুটোর সাথে, এবং count সম্পর্ক — সব মিললে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

4
3
5
সব test pass!

প্রথম: upper_bound(a, 3) = 4 (সব 3 পেরিয়ে)। দ্বিতীয়: count_of(a, 3) = 3 (upper 4 − lower 1)। তৃতীয়: upper_bound(a, 7) = 5 (সব 7 পেরিয়ে = len)। আগের সব assert (bisect_right, brute force, count যাচাই সহ) চুপচাপ pass। সবশেষে সব test pass!।

15. Time complexity

O(log n) — প্রতি ধাপে অর্ধেক, ঠিক 092-এর মতো। "x কয়বার আছে" বের করতে দুটো বার (lower + upper) চালালেও মোট O(log n)।

16. Space complexity

O(1) — শুধু lo, hi, mid; বাড়তি array লাগে না। (test-এর big list আলাদা।)

17. Common mistakes

1. < আর <= অদলবদল — সবচেয়ে কমন। lower bound-এ <, upper bound-এ <=। ভুল করলে duplicate-এ এক ঘর এদিক-ওদিক — কিন্তু x না থাকলে দুটোই একই দেয়, তাই bug চাপা পড়ে যায়।
2. count বের করতে upper - lower + 1 লেখা — না, ফারাকটাই সরাসরি count, +1 লাগে না (half-open interval)।
3. hi = len(a) - 1 দিয়ে শুরু — x সবচেয়ে বড় হলে উত্তর len(a) মিস হয়; range [0, len(a)] রাখো।
4. while lo <= hi লেখা — hi = mid থাকায় infinite loop। এই template-এ while lo < hi।
5. bisect_left আর bisect_right মনে রাখায় ভুল — bisect_left = lower (প্রথম ≥), bisect_right = upper (প্রথম >)। নাম থেকে ধরো: "left" = বাঁ ঘেঁষে = ≥; "right" = ডান ঘেঁষে = >।

18. Harder problems that inherit this idea

• LeetCode — Find First and Last Position (https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/) — first = lower bound, last = upper bound − 1; দুটো একসাথে।
• LeetCode — Count of Smaller Numbers After Self (https://leetcode.com/problems/count-of-smaller-numbers-after-self/) — "কয়টা ছোট" — bound-এর গোনার চিন্তা আরও গভীরে।
• 094 (Search Insert Position) আর 102 (Kth Smallest in Multiplication Table) — এই repo-রই পরের ধাপ; 102-এ "≤ x কয়টা" গোনার মূলে এই bound-চিন্তাই।

19. Pattern learned

Upper bound (first > x) via boundary search — lower bound-এর হুবহু কোড, শুধু < → <=। বড় শিক্ষা: শর্তে == ক্ষেত্রটা কোন দিকে ঠেলো, তাই ঠিক করে তুমি duplicate-এর বাঁয়ে না ডানে থামছ — আর upper − lower = count। এই জোড়া (092 + 093) হলো sorted data-তে গোনা-খোঁজার সবচেয়ে দরকারি হাতিয়ার।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "upper bound = প্রথম a[i] > x; lower bound-এর কোডে শুধু < → <=। = bisect_right। মনে রাখি: upper − lower = x কয়বার আছে। == ক্ষেত্র ডানে ঠেললে upper, বাঁয়ে রাখলে lower।"

পরের ধাপ → 094 — Search Insert Position (lower bound-এর সরাসরি ছদ্মবেশ)। সম্পর্কিত → 092 — Lower Bound (যমজ ভাই)।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।