Lecture from Strivers A to Z DSA course: Introduction to Arrays and Problem Solving

Introduction

• Strivers A to Z DSA course: In-depth DS algorithm course
• 456 modules, 400+ problems
• Goal: Clear any DS algorithm interviews

Arrays Basics

• Definition: Array is a data structure with similar elements (integers, characters, strings, etc.). Must be of the same data type.
• Declaration: In different languages
  • C++/Java: int array[6] or new int[6]
• Default Values:
  • Local (inside function): Garbage values
  • Global: Zeros
• Size:
  • Local Array: up to 10^6
  • Global Array: up to 10^7

Accessing Arrays

• Indexing: Starts from 0 to size-1
• Looping: From 0 to n-1
• Print example: Print all elements in an array by looping

Memory Storage

• Contiguous memory locations
• Random starting location x
• Indices stored at: x, x+1, x+2, etc.

Problem Solving with Arrays

Problem: Largest Element in Array

1. Brute Force Solution
   • Sort Array: Get the last element
   • Time complexity: O(n log n)
2. Optimal Solution
   • Single Pass: Track largest element
   • Time complexity: O(n)
   • Example code: largest = array[0] for i in range(1, n): if array[i] > largest: largest = array[i] print(largest)

Problem: Second Largest Element in Array

1. Brute Force Solution
   • Sort Array: Handle duplicate largest
   • Time complexity: O(n log n)
2. Better Approach
   • Two Passes:
     1. Find largest
     2. Find second largest excluding the largest
   • Time complexity: O(2n)
   • Example code: largest = array[0] for i in range(1, n): if array[i] > largest: largest = array[i] second_largest = -1 for i in range(1, n): if array[i] != largest and array[i] > second_largest: second_largest = array[i] print(second_largest)
3. Optimal Approach
   • Single Pass
   • Time complexity: O(n)
   • Example code: largest = array[0] second_largest = -1 for i in range(1, n): if array[i] > largest: second_largest = largest largest = array[i] elif array[i] > second_largest and array[i] != largest: second_largest = array[i] print(second_largest)

Problem: Check if Array is Sorted

• Simple Check
• Loop from index 1: Compare with the previous element
• Time complexity: O(n)
• Example code: for i in range(1, n): if array[i] < array[i - 1]: return False return True

Problem: Remove Duplicates from Sorted Array

1. Brute Force Solution
   • Use set for unique elements
   • Time complexity: O(n log n)
   • Space complexity: O(n)
2. Optimal Solution
   • Two Pointers
   • Single Pass: Arrange unique elements in-place
   • Time complexity: O(n)
   • Example code: i = 0 for j in range(1, n): if array[j] != array[i]: i += 1 array[i] = array[j] return i + 1

Conclusion

• Practice: Solve array problems
• Follow Steps: Brute force, better, optimal
• Next Lecture: Solve next 5 array problems