DSA Sheet - Day 4 Arrays

🚀 DSA Sheet – Day 4: Arrays (Part 4)

This set focuses on advanced concepts like Prefix Sum, Cycle Detection, and Matrix Traversal. These patterns are extremely common in real interviews — master them well.

📊 Progress Tracker

Progress: 0 / 5 Completed

Done	Problem	Practice	Level	Companies
	Subarray Sum Equals K	Solve	Medium	Microsoft, Snapdeal
	Find Duplicate Number	Solve	Medium	Adobe, Apple, Goldman Sachs
	Count Inversions	Solve	Hard	Amazon, Google, Salesforce
	Spiral Matrix	Solve	Medium	Apple, Flipkart
	Search in Sorted Matrix II	Solve	Medium	Amazon, Apple, TCS

🧠 Key Approaches

• Subarray Sum Equals K: Prefix sum + HashMap
• Find Duplicate: Floyd’s Cycle Detection (Linked List logic)
• Count Inversions: Merge Sort based counting
• Spiral Matrix: Boundary traversal technique
• Search in Matrix II: Start from top-right, eliminate rows/columns

⚡ Quick Cheatsheet

Subarray Sum Equals K

unordered_map mp;
mp[0] = 1;

int sum = 0, count = 0;

for(int x : nums){
  sum += x;

  if(mp.count(sum - k)) 
    count += mp[sum - k];

  mp[sum]++;
}
    

Find Duplicate (Floyd’s Cycle Detection)

int slow = nums[0], fast = nums[0];

do {
  slow = nums[slow];
  fast = nums[nums[fast]];
} while(slow != fast);

slow = nums[0];

while(slow != fast){
  slow = nums[slow];
  fast = nums[fast];
}

return slow;
    

Spiral Matrix

int top = 0, bottom = n - 1;
int left = 0, right = m - 1;

while(top <= bottom && left <= right){

  for(int i = left; i <= right; i++) 
    print(matrix[top][i]);
  top++;

  for(int i = top; i <= bottom; i++) 
    print(matrix[i][right]);
  right--;

  if(top <= bottom){
    for(int i = right; i >= left; i--) 
      print(matrix[bottom][i]);
    bottom--;
  }

  if(left <= right){
    for(int i = bottom; i >= top; i--) 
      print(matrix[i][left]);
    left++;
  }
}
    

🔥 Pro Tip

These problems introduce powerful real-world patterns:

• Prefix Sum Optimization
• Cycle Detection (Linked List trick in Arrays)
• Matrix Traversal Techniques

Once you master these, you’ll start recognizing hidden patterns in complex problems.

🏠 All Days ⬅ Previous Next ➡