beingsde
Sign In
Back to all DSA patterns
Array•Pattern: Index Marking•Medium

Find all duplicates in an array (values in [1, n])

Problem Intuition & Objective

Find every element that appears twice without extra space.

Time ComplexityO(n)
Optimal
Space ComplexityO(1)
Memory Bounds
Optimal Algorithmic Approach

Index-as-hash: mark visited positions by negating; a second visit to an already-negative slot reveals the duplicate.

Core Invariants & Edge Cases

  • Use array indices as a hash — negate nums[abs(nums[i])-1]
  • If already negative when you visit, that index+1 is a duplicate
  • Works only when values are in [1, n]
Previous ProblemContainer with Most WaterNext Problem Spiral order traversal of a matrix

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.