DSA Sheet - Day 1 Arrays

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

Start your DSA journey with the most important array problems asked in FAANG interviews. Focus on patterns, not just solutions.

📌 Practice Problems

• Majority Element — Easy
• Repeat & Missing Number — Easy
• Merge 2 Sorted Arrays — Easy
• Single Number — Easy
• Best Time to Buy & Sell Stock — Easy
• Pow(x, n) — Medium

🧠 Key Approaches

• Majority Element: Boyer-Moore Voting Algorithm (O(n), O(1))
• Repeat & Missing: XOR or Math equations
• Merge Arrays: Gap Method (Shell Sort idea)
• Single Number: XOR cancels duplicates
• Stock Buy & Sell: Track minimum price dynamically
• Pow(x, n): Binary Exponentiation

⚡ Quick Cheatsheet

Majority Element (Boyer-Moore)

int candidate = 0, count = 0;
for (int num : nums) {
  if (count == 0) candidate = num;
  count += (num == candidate) ? 1 : -1;
}
    

Single Number (XOR)

int res = 0;
for (int num : nums) res ^= num;
    

Stock Buy & Sell

int minPrice = INT_MAX, profit = 0;
for (int price : prices) {
  minPrice = min(minPrice, price);
  profit = max(profit, price - minPrice);
}
    

Pow(x, n) – Binary Exponentiation

double res = 1;
while (n) {
  if (n % 2) res *= x;
  x *= x;
  n /= 2;
}
    

🔥 Pro Tip

Arrays are the foundation of most interview questions. If you master these patterns, you’ll unlock:

• Sliding Window
• Prefix Sum
• Greedy Algorithms

🏠 All Days ⬅ Previous Next ➡