📚

Comprehensive DSA Course Lecture Notes

May 5, 2025

Strivers A2Z DSA Course Lecture Notes

Course Overview

  • The Strivers A2Z DSA course covers data structures and algorithms in depth.
  • Total of 456 modules and 400+ problems to be solved.
  • Aim: Clear any data structures and algorithms rounds in interviews worldwide.

Previous Progress

  • Covered up to Step 3.1 and the fourth problem.
  • This session will cover five new problems.

Problem 1: Left Rotate an Array by One Place

Explanation

  • Left rotation means moving each element of the array to the left by one position, wrapping around the first element to the end.
  • Example: For array [1, 2, 3, 4, 5], the left rotated array is [2, 3, 4, 5, 1].

Approach

  1. Brute Force: Create a new array to store the rotated version (not required for this problem).
  2. Optimal Solution:
    • Use a temporary variable to store the first element.
    • Shift all elements left by one position.
    • Place the stored element at the end of the array.

Implementation

# Pseudocode def leftRotate(arr): temp = arr[0] # Store the first element for i in range(1, len(arr)): arr[i-1] = arr[i] # Shift elements left arr[-1] = temp # Place the first element at the end

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(1) (extra space used is constant)

Problem 2: Left Rotate an Array by D Places

Explanation

  • Similar to the first problem, but rotate by D positions.
  • Example: For D=2, the array [1, 2, 3, 4, 5] becomes [3, 4, 5, 1, 2].

Approach

  1. Brute Force: Perform D left rotations using the first problem approach.
  2. Optimal Solution:
    • Calculate D = D % N to handle cases where D is greater than array size.
    • Reverse the first N-D, then reverse the last D, and finally reverse the entire array.

Implementation

# Pseudocode def leftRotateByD(arr, D): D = D % len(arr) # Handle D greater than N reverse(arr, 0, len(arr)-1) reverse(arr, 0, len(arr)-D-1) reverse(arr, len(arr)-D, len(arr)-1)

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(1)

Problem 3: Move Zeros to the End

Explanation

  • Move all zeros in an array to its end while maintaining the order of non-zero elements.
  • Example: [0, 1, 0, 3, 12] becomes [1, 3, 12, 0, 0].

Approach

  1. Brute Force: Create a new array and store all non-zero elements followed by zeros.
  2. Optimal Solution: Use a two-pointer technique to swap non-zero elements with zeros directly in the array.

Implementation

# Pseudocode def moveZeros(arr): lastNonZero = 0 for i in range(len(arr)): if arr[i] != 0: arr[lastNonZero], arr[i] = arr[i], arr[lastNonZero] lastNonZero += 1

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(1)

Problem 4: Linear Search

Explanation

  • Find the first occurrence of a given number in an array.
  • Return the index or -1 if not found.

Approach

  • Iterate through the array comparing each element to the target.
  • Return the index of the first match or -1 if no match is found.

Implementation

# Pseudocode def linearSearch(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(1)

Problem 5: Union of Two Sorted Arrays

Explanation

  • Given two sorted arrays, return an array with their union without duplicates.

Approach

  1. Brute Force: Use a set to insert all elements from both arrays.
  2. Optimal Solution: Use a two-pointer approach, iterating over both arrays simultaneously.

Implementation

# Pseudocode def union(arr1, arr2): i = j = 0 result = [] while i < len(arr1) and j < len(arr2): if arr1[i] < arr2[j]: result.append(arr1[i]) i += 1 elif arr1[i] > arr2[j]: result.append(arr2[j]) j += 1 else: result.append(arr1[i]) # or arr2[j] i += 1 j += 1 return result

Complexity

  • Time Complexity: O(N1 + N2)
  • Space Complexity: O(N1 + N2) (for the result array)

Problem 6: Intersection of Two Sorted Arrays

Explanation

  • Find the intersection of two sorted arrays.

Approach

  • Similar to union, but only include duplicates that appear in both arrays.

Implementation

# Pseudocode def intersection(arr1, arr2): i = j = 0 result = [] while i < len(arr1) and j < len(arr2): if arr1[i] < arr2[j]: i += 1 elif arr1[i] > arr2[j]: j += 1 else: result.append(arr1[i]) i += 1 j += 1 return result

Complexity

  • Time Complexity: O(N1 + N2)
  • Space Complexity: O(min(N1, N2)) (for the result array)

Conclusion

  • Covered a total of nine problems related to arrays.
  • Suggested to practice rotating an array by D places as an assignment.
  • Encouraged to like, subscribe, and follow on social media for more content.

Full transcript