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