DAY 017 min readO(1)

Interviewer पूछेगा:

Array में 10 लाख elements हैं. 7 लाख वाला निकालने में कितना time लगेगा?

Cinema की seat. Memory का secret. Let’s make it click.

भाई, cinema hall में seat 7 की ticket मिली. अब क्या हर seat गिनते हुए जाओगे? नहीं ना. Row देखोगे, number देखोगे, और सीधे अपनी seat पर. Array भी यही करता है — बस seat की जगह memory address है.

Array = numbered seats, साथ-साथ

Array के elements contiguous memory में रहते हैं. अगर integer 4 bytes का है और पहला element address 1000 पर है, तो अगला 1004, फिर 1008, फिर 1012. हर element की width तय है, इसलिए index से उसकी location निकाल सकते हैं.

Seat 7 का address: 1000 + 7 × 4 = 1028. यहाँ index zero-based है. मतलब 7 वाला index आठवाँ element है. Interview में ‘7 लाखवाँ element’ और ‘index 7 लाख’ का अंतर clarify कर लेना.

address = base + index × element_size

7 हो या 7,00,000 — काम वही

Index 7 के लिए एक multiplication और एक addition. Index 7,00,000 के लिए भी वही. काम input के size के साथ नहीं बढ़ा, इसलिए random access O(1) है. इसका मतलब literally एक CPU instruction या एक nanosecond नहीं; यह growth rate की बात है.

लेकिन unknown value ढूँढनी हो तो index पहले से नहीं पता. Unsorted array में हर element check करना पड़ सकता है: O(n). Access by index और search by value को mix मत करना.

Read / update by known index: O(1).
Unsorted search: O(n).
Middle में insert / delete: O(n), क्योंकि आगे के elements shift होते हैं.
Dynamic array append: amortized O(1); resizing वाला particular append O(n).

Contiguous का मतलब हर language में बिल्कुल same?

C++ vector<int> में values contiguous हैं; Java int[] में primitive slots contiguous हैं. Python list में contiguous references होते हैं — actual integer objects अलग जगह हो सकते हैं. फिर भी list indexing O(1) रहती है, क्योंकि reference slot सीधे मिलता है.

Linked list में हर node next का address रखता है. Index 7 चाहिए तो links follow करने पड़ते हैं. वहाँ random access O(n) है. Data structure चुनते समय यही trade-off देखो.

Pattern unlock: Missing Number और prefix/suffix

Missing Number में range 0..n है और एक number missing है. सभी indices और values का XOR करो. x ^ x = 0, इसलिए pairs cancel होंगे और missing number बचेगा. Sum formula भी चलता है, पर fixed-width integers में overflow सोचो.

Product Except Self में हर index के left का product और right का product जोड़ना नहीं, multiply करना है. पहले prefix pass, फिर suffix pass. Division की जरूरत नहीं; zero values भी सही handle होंगी. Output array को छोड़कर extra space O(1).

INTERVIEW में बोलो · तुम्हारा ANSWER

“Array के elements fixed-size contiguous slots में होते हैं. Known index का address base + index × size से मिलता है. Input 10 elements का हो या 10 लाख का, calculation constant रहती है, इसलिए indexed access O(1). लेकिन value search करना unsorted array में O(n) है.”

Read it once. फिर अपने words में बोल के देखो.

SPOT IT BEFORE YOU CODE IT

Pattern पहचानो.

Problem में ये दिखे	तब ये use करो	यहाँ नहीं
Known index, random access	Array / dynamic array	Frequent middle insertions with known nodes
0..n, one missing	XOR / range invariant	Several missing values without adjusting the invariant
Except self, no division	Prefix + suffix products	An unrelated order-dependent problem

SAME LOGIC. YOUR LANGUAGE.

अब code लिखते हैं.

Missing Number · LC 268

XOR pairs cancel. O(n) time, O(1) extra space.

def missing_number(nums):
    missing = len(nums)
    for i, value in enumerate(nums):
        missing ^= i ^ value
    return missing

assert missing_number([3, 0, 1]) == 2

Product of Array Except Self · LC 238

Two passes. No division. O(n) time; O(1) extra space excluding output.

def product_except_self(nums):
    result = [1] * len(nums)
    prefix = 1
    for i, value in enumerate(nums):
        result[i] = prefix
        prefix *= value
    suffix = 1
    for i in range(len(nums) - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]

WATCHING ISN’T SOLVING. YOUR TURN.

Practice करो. Confidence आएगा.

YOUR PRACTICE BOARD0 / 3 solved

#268 Missing NumberXOR cancellationEasy

#238 Product of Array Except SelfPrefix / suffixMedium

#41 First Missing PositiveIn-place index mappingHard

Your progress stays on this device. Solve first, tick later. तू खुद से cheat मत करना.

कल interview है? ये साथ ले जाओ.

Day 1 का full guide — concepts, patterns, code और practice, एक PDF में.

अभी भी doubt है?

Array access और array search same नहीं?+

नहीं. arr[7] में location पता है. ‘Value 7 कहाँ है?’ में location unknown है. पहला O(1), दूसरा unsorted array पर worst-case O(n).

Index out of bounds हुआ तो?+

Language के हिसाब से exception या undefined behavior. Access से पहले 0 <= index < length validate करो. O(1) valid indices के लिए है.

Index पता है? Calculate करो, count नहीं. अगला pattern: sorted data में आधा काम गायब करना.

UP NEXT / DAY 02Binary search. Half the drama.

Seat number पता है?सीधे वहाँ जाओ.