Skip to content

004 — Remove Duplicates from Sorted Array

Source

  • Original source: Classic two-pointer (slow/fast) exercise
  • Platform: LeetCode — https://leetcode.com/problems/remove-duplicates-from-sorted-array/
  • Topic: array
  • Difficulty: Easy
  • Pattern: two pointers (slow/fast, same direction)
  • Basic idea inherited from: two-pointer reversal-এর idea — দুটো index, কিন্তু এবার একই দিকে

1. Problem in simple words

একটা sorted (বাড়ন্ত order-এ সাজানো) integer array nums দেওয়া। প্রতিটা আলাদা value যেন শুধু একবার থাকে — duplicate গুলো in place সরিয়ে দাও। কতগুলো unique value আছে (k) সেটা ফেরত দাও, আর nums-এর প্রথম k ঘরে সেই unique value গুলো order ঠিক রেখে বসিয়ে দাও। k-এর পরে কী আছে তা matter করে না।

nums = [1, 1, 2]  ->  k = 2, nums প্রথম 2 ঘর = [1, 2]

2. Which basic idea does this inherit from?

ভিত problem 1-এর two-pointer idea — তবে সেখানে দুই pointer দুই প্রান্ত থেকে আসত, এখানে দুটোই একই দিকে চলে: একটা slow (কোথায় পরের unique বসবে) আর একটা fast (array scan করছে)। same-direction slow/fast হলো array compaction-এর মূল কঙ্কাল।

3. What is the hidden math or logic?

লুকানো logic একটা invariant: nums[0..slow] সবসময় এ পর্যন্ত পাওয়া unique value গুলো, order ঠিক রেখে। array sorted বলে সব duplicate পাশাপাশি — তাই নতুন value চেনা সহজ: nums[fast] যদি nums[slow]-এর সমান না হয়, তবেই সেটা নতুন।

4. Which data structure is needed?

কোনো extra data structure লাগে না — array টা আছে, আর শুধু দুটো integer pointer (slow, fast)। O(1) extra space।

5. Why this data structure fits

array index দিয়ে O(1) read/write দেয়, তাই nums[fast]-কে সরাসরি nums[slow+1]-এ লিখে দেওয়া যায় কোনো shifting ছাড়াই। sorted property থাকায় duplicate detect করতে শুধু পাশের ঘরের সাথে তুলনা — set/dict-এর দরকারই নেই।

6. Real-life analogy

একসারি অতিথি লাইন ধরে আসছে, name অনুযায়ী আগে থেকে সাজানো। তুমি একটা guest book-এ প্রতিটা নাম একবারই লিখতে চাও। নতুন কেউ এলে তার নাম তোমার লেখা শেষ নামের সাথে মেলাও — আলাদা হলেই কেবল নতুন লাইনে লেখো; একই হলে এড়িয়ে যাও।

7. Visual explanation

nums = [0, 0, 1, 1, 2]:

slow নির্দেশ করে শেষ unique-এর জায়গা; fast scan করে।

start: slow=0  [ (0) 0  1  1  2 ]   fast=1
f=1: nums[1]=0 == nums[slow]=0 -> skip
f=2: nums[2]=1 != 0 -> slow=1; nums[1]=1  [0,(1),1,1,2]
f=3: nums[3]=1 == nums[slow]=1 -> skip
f=4: nums[4]=2 != 1 -> slow=2; nums[2]=2  [0,1,(2),1,2]

k = slow+1 = 3 ; প্রথম 3 ঘর = [0,1,2]

8. Example input and output

Input : [1, 1, 2]              -> k = 2, nums[:2] = [1, 2]
Input : [0,0,1,1,1,2,2,3,3,4]  -> k = 5, nums[:5] = [0,1,2,3,4]

Edge case (খালি): [] -> k = 0

9. Brute force thinking

প্রথম সরল চিন্তা: একটা set-এ unique গুলো রাখো, তারপর sort করে আবার nums-এ ফেরত লিখি।

unique = sorted(set(nums))
nums[:len(unique)] = unique
return len(unique)

10. Why brute force is slow

set বানালে O(n) extra space, আর sorted set আবার O(n log n) — অথচ array already sorted, sort একদম বাড়তি কাজ। problem চায় O(1) extra space, in place; পাশের ঘরের তুলনাই যথেষ্ট, পুরো set বানানোর দরকার নেই।

11. Key observation

মূল observation: array sorted বলে কোনো value-র সব copy টানা পাশাপাশি বসে আছে। তাই duplicate চিনতে দূরের কিছু মনে রাখার দরকার নেই — শুধু "এইটা কি ঠিক-আগে লেখা unique-এর সমান?" এটুকুই।

12. Optimized intuition

slow শুরুতে 0 (প্রথম element তো নিশ্চিত unique)। fast 1 থেকে শেষ পর্যন্ত হাঁটে। প্রতিবার nums[fast] != nums[slow] হলে নতুন value পেলাম → slow এক বাড়িয়ে সেখানে nums[fast] লিখি। শেষে unique সংখ্যা slow + 1।

13. Thinking tweak

মোচড়: "duplicate মুছব" (যা shifting চায়) ভাবার বদলে ভাবো "unique গুলো সামনে নতুন করে লিখব।" তখন delete-এর O(n) shift গায়েব; একটা write-pointer দিয়ে এক pass-এই হয়ে যায়।

14. Step-by-step dry run

Input [1, 1, 2]:

  1. শুরু: slow=0 (nums[0]=1 ধরে নিলাম unique)।
  2. fast=1: nums[1]=1 == nums[slow]=1 → duplicate, skip।
  3. fast=2: nums[2]=2 != nums[slow]=1 → slow=1; nums[1]=2। array এখন [1,2,2]।
  4. loop শেষ। k = slow + 1 = 2; প্রথম 2 ঘর [1, 2]।

15. Python solution

def remove_duplicates(nums):
    if not nums:                       # খালি array
        return 0
    slow = 0                           # শেষ unique-এর index
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:   # নতুন value পেলাম
            slow += 1
            nums[slow] = nums[fast]    # সামনে লিখে দাও
    return slow + 1                    # unique-এর সংখ্যা

# ---- tests ----
nums = [1, 1, 2]
k = remove_duplicates(nums)
assert k == 2 and nums[:k] == [1, 2]

nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k2 = remove_duplicates(nums2)
assert k2 == 5 and nums2[:k2] == [0, 1, 2, 3, 4]

assert remove_duplicates([]) == 0      # খালি array
print("সব test pass!")

16. Line-by-line code explanation

  • if not nums: return 0 — খালি array হলে unique 0।
  • slow = 0 — প্রথম element আপনাআপনি unique, তাই write-pointer 0-তে।
  • for fast in range(1, len(nums)) — দ্বিতীয় element থেকে scan।
  • if nums[fast] != nums[slow] — sorted বলে পাশের সাথে আলাদা মানেই নতুন।
  • slow += 1; nums[slow] = nums[fast] — নতুন unique-কে সামনের ঘরে বসাই।
  • return slow + 1 — index slow পর্যন্ত ভরা, তাই গুনতি slow + 1।

17. Output walkthrough

[1,1,2]: fast=1 duplicate skip, fast=2 নতুন → nums=[1,2,2], slow=1, k=2, nums[:2]=[1,2] — assert pass। বড় array দেয় k=5, [0,1,2,3,4]। খালি দেয় 0। শেষে print: সব test pass!।

18. Time complexity

O(n) — fast array-র উপর ঠিক একবার হাঁটে; প্রতিটা step O(1)।

19. Space complexity

O(1) — শুধু দুটো pointer; array-র ভেতরেই overwrite হয়।

20. Common mistakes

  • খালি array আলাদা না ধরা — slow=0 ধরে slow+1=1 ভুল ফেরত দিত।
  • nums[fast]-কে আগের লেখা unique (nums[slow])-এর বদলে দূরের কিছুর সাথে তুলনা করা — sorted বলে পাশের তুলনাই যথেষ্ট।
  • slow বাড়ানো আর লেখার order উল্টে ফেলা — তখন value চাপা পড়ে যায়।

21. Which basic problem this inherits from

ভিত্তি: problem 1-এর two-pointer, এখন same-direction slow/fast রূপে। এই একই কঙ্কাল move zeroes (#6)-এও — শুধু "নতুন কিনা" শর্তের জায়গায় "zero নয় কিনা"। chapter-এর ../patterns.md-এর "Pattern 1 — Two Pointers" দেখো।

22. Similar harder problems

23. Pattern learned

Slow/fast two pointers (in-place compaction): একটা write-pointer রাখা value সামনে আনে, একটা read-pointer scan করে — delete-এর O(n) shift এড়িয়ে এক pass।

24. Final summary

ভবিষ্যতের আমাকে: "in place duplicate/element সরানো = slow write-pointer + fast read-pointer।" "remove in place, keep order" দেখলেই এই slow/fast দুই-pointer মনে করবে।

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