DSA for Data Engineers

Two Sum : Given an array of integers and a target, return the indices of two numbers that add up to the target. Use a hash map to store each number's in...

• https://leetcode.com/problems/two-sum/description/

  Two Sum : Given an array of integers and a target, return the indices of two numbers that add up to the target. Use a hash map to store each number's index as you iterate, checking if the complement exists. Time complexity : O(n) single pass through the array Space complexity : O(n) hash map stores up to n elements

• https://leetcode.com/problems/subarray-sum-equals-k/description/

  Subarray Sum Equals K : Count the number of contiguous subarrays whose sum equals k. Use a prefix sum with a hash map tracking how many times each prefix sum has occurred. Time complexity : O(n) single pass Space complexity : O(n) hash map for prefix sums Key insight : If prefix sum[j] prefix sum[i] == k , then the subarray from i+1 to j sums to k

• https://leetcode.com/problems/find-the-duplicate-number/description/

  Find the Duplicate Number : Given an array of n+1 integers in the range [1, n], find the one duplicate without modifying the array. Use Floyd's cycle detection (tortoise and hare) by treating values as pointers. Time complexity : O(n) Space complexity : O(1) no extra space Why it works : The array can be viewed as a linked list where nums[i] points to the next node. A duplicate value means two nodes point to the same node, creating a cycle.

• https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

  Best Time to Buy and Sell Stock : Find the maximum profit from a single buy sell transaction. Track the minimum price seen so far and compute the profit at each step. Time complexity : O(n) single pass Space complexity : O(1) Key insight : At each day, the best profit is the current price minus the lowest price seen before today

• https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/

  Best Time to Buy and Sell Stock II : Maximize profit with unlimited transactions (buy and sell multiple times). Collect every upward price movement by summing all positive differences between consecutive days. Time complexity : O(n) Space complexity : O(1) Key insight : Buying at every local minimum and selling at every local maximum is equivalent to summing all positive consecutive differences

• https://leetcode.com/problems/max-consecutive-ones/description/

  Max Consecutive Ones : Find the maximum number of consecutive 1s in a binary array. Use a simple counter that resets on encountering a 0. Time complexity : O(n) Space complexity : O(1)

• https://leetcode.com/problems/max-consecutive-ones-iii/description/

  Max Consecutive Ones III : Find the longest subarray of 1s after flipping at most k zeros. Use a sliding window that expands right and shrinks left when the zero count exceeds k. Time complexity : O(n) each element is visited at most twice Space complexity : O(1) Pattern : Classic sliding window expand right, shrink left when constraint is violated

• https://leetcode.com/problems/maximum-subarray/description/

  Maximum Subarray : Find the contiguous subarray with the largest sum. Use Kadane's algorithm : maintain a running sum and reset it when it goes negative. Time complexity : O(n) Space complexity : O(1) Key insight : At each position, either extend the existing subarray or start a new one from the current element. If the running sum becomes negative, starting fresh is always better.