020 — House Robber on a Circle¶

Source¶

Original source: Classic take-or-skip DP exercise, circular variant
Platform: LeetCode — "House Robber II" at https://leetcode.com/
Topic: dynamic programming (1D + case split)
Difficulty: Hard
Pattern: 1D take-or-skip DP + case split
Basic idea inherited from: #6 House Robber — একই take-or-skip core, কিন্তু বাড়িগুলো বৃত্তে বলে প্রথম আর শেষ বাড়ি adjacent; trick হলো linear robber-টা দুবার চালানো

1. Problem in simple words¶

6-এর মতোই বাড়ির array `nums`, প্রত্যেকটায় কিছু টাকা, পাশাপাশি দুটো লুট করা যাবে না। কিন্তু এবার বাড়িগুলো বৃত্তে সাজানো — মানে প্রথম বাড়ি (index 0) আর শেষ বাড়ি (index n-1) একে অপরের পাশে, তাই দুটো একসাথে লুট করা যাবে না। সর্বোচ্চ কত টাকা লুট করতে পারবে?¶

nums = [2, 3, 2]   (বৃত্তে: 2 - 3 - 2 - আবার 2-তে ফেরে)
বাড়ি 0 আর 2 দুটোই 2, কিন্তু adjacent (বৃত্ত), তাই একসাথে নয়।
সবচেয়ে ভালো: শুধু বাড়ি 1 (3) -> 3

2. Which basic idea does this inherit from?¶

ভিত্তি সরাসরি #6 House Robber-এর take-or-skip core: dp[i] = max(dp[i-1], dp[i-2] + nums[i])। নতুন জিনিস শুধু একটা constraint — প্রথম আর শেষ বাড়ি adjacent। মূল চালাকি: বৃত্তটাকে দুটো লাইনে কাটো — একটায় শেষ বাড়ি বাদ, আরেকটায় প্রথম বাড়ি বাদ — তাহলে প্রতিবার #6-এর সাধারণ linear robber-ই চালানো যায়, আর দুটোর max নিলেই উত্তর।

3. What is the hidden math or logic?¶

লুকানো logic একটা সরল case split: optimal solution-এ হয় বাড়ি 0 লুট হয়েছে, নয় হয়নি — দুটো একসাথে নয়, এবং অন্তত একটা সত্যি। বাড়ি 0 লুট হলে বাড়ি n-1 নিষিদ্ধ; তাই nums[0..n-2]-এর উপর সাধারণ linear robber চালাও। বাড়ি 0 না হলে n-1 মুক্ত; তাই nums[1..n-1]-এর উপর চালাও। দুটোর max-ই গোটা বৃত্তের উত্তর — কারণ প্রতিটা case থেকে "0 আর n-1 একসাথে" সম্ভাবনাটা বাদ পড়েছে।

4. Which data structure is needed?¶

কিছুই নতুন নয় — #6-এর linear robber-ই lএকটা helper function হিসেবে রাখো, যেটা একটা slice-এর উপর O(1) space-এ (দুটো rolling variable) চলে। মূল function শুধু দুবার সেই helper ডাকে আর max নেয়। চাইলে একটা dp array, কিন্তু rolling দুই variable-ই যথেষ্ট।

5. Why this data structure fits¶

State আসলে #6-এর মতোই — "কত নম্বর বাড়ি পর্যন্ত best লুট" — শুধু দুটো আলাদা window-তে। তাই flat slice-এর উপর rolling DP নিখুঁত। বৃত্তের জটিলতাটা data structure-এ ঢোকে না; সেটা একটা উঁচু স্তরের case split-এ সামলানো হয়, তাই ভেতরের যন্ত্র সরল থাকে।

6. Real-life analogy¶

ভাবো বাড়িগুলো একটা গোল মাঠের ধার ঘিরে। তুমি জানো প্রথম বাড়ি ছুঁলে শেষ বাড়ি ছোঁয়া যাবে না (ওরা পাশাপাশি)। তাই দুটো পরিকল্পনা করো: পরিকল্পনা A — "আমি প্রথম বাড়ি ছুঁতে পারি বলে ধরি, তাই শেষ বাড়িটা পরিকল্পনা থেকে কেটে দিই"; পরিকল্পনা B — "আমি প্রথম বাড়ি ছুঁব না, তাই শেষ বাড়ি খোলা রাখি, কিন্তু প্রথমটা কেটে দিই।" দুটো সরল সারি-লুটের হিসাব কষে বড়টা বেছে নাও।

7. Visual explanation¶

nums = [2, 7, 9, 3, 1] (বৃত্তে)। দুটো linear সমস্যায় ভাঙো:

circle: 2 - 7 - 9 - 3 - 1 - (back to 2)
        ^                 ^
       house 0          house 4  (adjacent)

case A (drop last):  rob_line([2, 7, 9, 3])     # বাড়ি 0 ছুঁতে পারি
case B (drop first): rob_line([7, 9, 3, 1])     # বাড়ি 4 ছুঁতে পারি

answer = max(case A, case B)

rob_line(a):  dp[i] = max(dp[i-1], dp[i-2] + a[i])   # ঠিক #6

case A → 2 + 9 = 11; case B → 7 + 3 = 10 (বা 9 + 1 = 10); max = 11।

8. Example input and output¶

Input : nums = [2, 3, 2]       -> Output: 3   (শুধু 3; 0 আর 2 adjacent)
Input : nums = [1, 2, 3, 1]    -> Output: 4   (1 + 3)
Input : nums = [2, 7, 9, 3, 1] -> Output: 11  (2 + 9)

Edge case 1: nums = [5]        -> Output: 5   (এক বাড়ি)
Edge case 2: nums = [2, 3]     -> Output: 3   (দুই বাড়ি, বড়টা)
Edge case 3: nums = [1, 2, 3]  -> Output: 3   (0,2 adjacent -> মাঝেরটা বা একটা প্রান্ত)

9. Brute force thinking¶

প্রথম সরল চিন্তা: সব valid subset দেখো (কোনো দুটো adjacent নয়, এবং 0 ও n-1 একসাথে নয়), max sum নাও।

সব subset S of houses:
    if কোনো দুটো S-member পাশাপাশি নয় (বৃত্ত-অর্থে):
        track sum(S)
answer = max sum

10. Why brute force is slow¶

সব subset enumerate করা O(2^n) — exponential, আর প্রতিটায় adjacency check। বৃত্ত-constraint যোগ করায় শুধু আরও জটিল হয়, দ্রুত হয় না। অথচ আমরা জানি linear robber O(n)-এ হয় (#6), তাই বৃত্তটাকেও দুটো linear-এ ভেঙে O(n)-এ সারা যায়।

11. Key observation¶

মূল observation: শুধু একটা জোড়াই (0, n-1) লাইনের চেয়ে বেশি constraint যোগ করে। আর "0 আর n-1 একসাথে নয়" সমান "অন্তত একটা বাদ"। তাই দুটো case — "n-1 বাদ" আর "0 বাদ" — মিলে সব valid সমাধান ধরে, প্রতিটাই একটা সাধারণ linear robber।

12. Optimized intuition¶

State (শব্দে): helper rob_line(a)-এর ভেতর — dp[i] = slice a-র বাড়ি 0..i থেকে সম্ভব max লুট (ঠিক #6)। বাইরের answer = দুই slice-এর rob_line-এর max।

Transition (helper-এর ভেতর):

dp[i] = max(dp[i-1],            # skip house i
            dp[i-2] + a[i])      # rob it -> i-1 নিষিদ্ধ

Case split (বাইরে):

if n == 1: return nums[0]
answer = max( rob_line(nums[0 : n-1]),   # শেষ বাড়ি বাদ
              rob_line(nums[1 : n])  )    # প্রথম বাড়ি বাদ

Base case: helper-এ dp[0]=a[0], dp[1]=max(a[0],a[1]); বাইরে single-house আলাদা।

Answer location: দুই helper-call-এর max।

13. Thinking tweak¶

মোচড়: বৃত্তের wrap-around constraint-কে সরাসরি DP state-এ ঢোকানোর চেষ্টা কোরো না — সেটা messy। বদলে একটা উঁচু-স্তরের সিদ্ধান্তে ("0 ছোঁব কি ছোঁব না") problem-টাকে দুটো পরিচিত linear সমস্যায় কেটে ফেলো। কঠিন constraint-কে কয়েকটা সরল case-এ ভাগ করা — এটা অনেক "circular / wrap-around" problem-এর সাধারণ অস্ত্র।

14. Step-by-step dry run¶

nums = [1, 2, 3]:

n = 3, single-house নয়
case A rob_line([1, 2]): dp[0]=1, dp[1]=max(1,2)=2 → 2
case B rob_line([2, 3]): dp[0]=2, dp[1]=max(2,3)=3 → 3
answer = max(2, 3) = 3

হাতে মিলিয়ে: 0 আর 2 adjacent (বৃত্ত), তাই একসাথে 1+3 নেওয়া যায় না; সেরা single হলো বাড়ি 2 (3)। ✔

15. Python solution¶

# ---- helper: linear House Robber (#6), O(1) space ----
def rob_line(a):
    take, skip = 0, 0                        # take = best ending using last; skip = best skipping last
    for x in a:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)

# ---- way 1: case split (drop first OR drop last) ----
def rob_circle(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    return max(rob_line(nums[: n - 1]),      # শেষ বাড়ি বাদ
               rob_line(nums[1:]))           # প্রথম বাড়ি বাদ

# ---- way 2: explicit dp-array helper (same logic, array form) ----
def rob_line_arr(a):
    if not a:
        return 0
    if len(a) == 1:
        return a[0]
    dp = [0] * len(a)
    dp[0] = a[0]
    dp[1] = max(a[0], a[1])
    for i in range(2, len(a)):
        dp[i] = max(dp[i - 1], dp[i - 2] + a[i])
    return dp[-1]

def rob_circle_arr(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    return max(rob_line_arr(nums[: n - 1]),
               rob_line_arr(nums[1:]))

# ---- tests ----
cases = [
    ([2, 3, 2], 3),
    ([1, 2, 3, 1], 4),
    ([2, 7, 9, 3, 1], 11),
    ([5], 5),
    ([2, 3], 3),
    ([1, 2, 3], 3),
    ([200, 3, 140, 20, 10], 340),   # 200 + 140
    ([0, 0, 0], 0),
]
for nums, want in cases:
    assert rob_circle(nums) == want, (nums, rob_circle(nums))
    assert rob_circle_arr(nums) == want, (nums, rob_circle_arr(nums))

print("সব test pass!")

16. Line-by-line code explanation¶

rob_line: #6-এর O(1) robber; take = এই element নিয়ে best, skip = এটা বাদ দিয়ে best; এক assignment-এ এগোয়, শেষে max।
rob_circle: খালি ও single-house আলাদা; নয়তো দুই slice ([:n-1] শেষ বাদ, [1:] প্রথম বাদ)-এর rob_line-এর max।
rob_line_arr / rob_circle_arr: একই algorithm, কিন্তু helper-এ explicit dp array — দেখায় rolling আর array দুই form-ই একই উত্তর দেয়।

17. Output walkthrough¶

cases-এ আটটা input: [2,3,2] (3, কারণ প্রান্ত-দুটো adjacent), [1,2,3,1] (4), classic [2,7,9,3,1] (11), single (5), দুই-বাড়ি (3), [1,2,3] (3), একটা bigger [200,3,140,20,10] (200+140 = 340), আর সব-শূন্য (0)। প্রতিটার জন্য দুই function-ই (rolling + array) একই উত্তর দিতে হবে। সব pass হলে শেষে print: সব test pass!।

18. Time complexity¶

দুই version-ই O(n) — helper দুবার চলে, প্রতিবার O(n)। (Naive subset enumeration ছিল O(2^n)।)

19. Space complexity¶

rob_circle (rolling helper): O(n) শুধু slice তৈরির জন্য, helper নিজে O(1); চাইলে index-range পাঠিয়ে slice-ও এড়ানো যায়।
rob_circle_arr: O(n) — dp array।

20. Common mistakes¶

single-house edge না সামলানো — n == 1-এ slice nums[:0] খালি হয়ে answer ভুল 0 দেয়; আলাদা return লাগে।
দুটো case-এর বদলে শুধু একটা চালানো (যেমন শুধু "শেষ বাদ") — তখন এমন সমাধান হারাবে যেখানে শেষ বাড়িই সেরা।
প্রথম আর শেষ "একসাথে নয়" নিয়মটা ভুলে গিয়ে সাধারণ linear robber চালানো — তখন [2,3,2]-এ ভুল করে 4 (2+2) আসবে।

21. Which basic problem this inherits from¶

ভিত্তি: #6 House Robber-এর take-or-skip core, একটা case split দিয়ে মুড়ে। #6-এর note আর ../state-transition-thinking.md-এর "Problem 2 — House Robber"-এই linear DP-টা আছে; এখানে শুধু বৃত্ত-constraint-এর জন্য দুবার চালানো।

22. Similar harder problems¶

House Robber III (বাড়িগুলো গাছে, tree DP) — https://leetcode.com/problems/house-robber-iii/
Delete and Earn (value বানিয়ে take-or-skip) — https://leetcode.com/problems/delete-and-earn/
Maximum Sum Circular Subarray (একই "circular = দুই case" কৌশল) — https://leetcode.com/problems/maximum-sum-circular-subarray/

23. Pattern learned¶

Circular = case split into linear: wrap-around constraint থাকলে একটা প্রান্ত-উপাদান নিয়ে binary সিদ্ধান্ত নাও ("নেব / নেব না"), আর প্রতিটা case-কে আগের পরিচিত linear সমাধানে নামিয়ে আনো; দুটোর max-ই উত্তর। বৃত্ত-জটিলতাকে DP state-এ না ঢুকিয়ে উঁচু স্তরে সামলানো।

24. Final summary¶

ভবিষ্যতের আমাকে: "House Robber II = linear robber দুবার।" বৃত্তটাকে কাটো: একবার শেষ বাড়ি বাদ, একবার প্রথম বাড়ি বাদ — দুই linear robber চালিয়ে max নাও; single-house আলাদা। মনে রেখো: circular/wrap-around constraint প্রায়ই একটা ছোট case split-এ সরল linear সমস্যায় ভেঙে যায়।

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