DSA-Task-

For Any Doubt 💬

Reach out to Piyush at 6397415707 Or Parth at 9559805577.

Week 1 Task: Let's Master "Subarray" Related Problems 🚀

1. Understand the Problem Clearly:

• Carefully read the problem and break it down.
• Are you asked to find a subarray with certain properties (e.g., smallest, largest sum, divisible sum)?
• Are you asked to maximize, minimize, or check for the existence of a condition?
• Does the problem allow for negative numbers or only positive ones?

Understanding these questions is the first step towards identifying which algorithm or technique might work best for solving the problem.

---

2. Analyze the Subarray Nature:

Subarrays are contiguous parts of an array, and different categories of subarray-related problems exist.

• Key Point: Each category has specific patterns and hints towards a particular type of solution, so recognizing the subarray nature in the problem is crucial.

---

3. Look for Common Patterns:

1) Sliding Window or Two-Pointer Technique:

• When to Use:

  • Finding a subarray with a fixed sum or length.
  • Finding a subarray with conditions that can be checked as you move from one end of the array to another.

• Why It Works: This technique is efficient because it processes the array in linear time, expanding and contracting the window as needed.

• Common Problem Types:

  • Finding the smallest subarray with a sum greater than X.
  • Longest subarray with distinct elements or fixed-length subarrays.

• Example:

  • If you’re asked to find the longest subarray with sum ≤ k, sliding window is often the best approach.

---

2) Kadane’s Algorithm (Dynamic Programming):

• When to Use:

  • Finding the maximum subarray sum.

• Why It Works:

  • This algorithm efficiently tracks the maximum subarray sum ending at each index.
  • It's optimal as it builds solutions to subproblems (maximum sums ending at earlier indices) and extends them to solve larger problems.

• Common Problem Types:

  • Finding the maximum subarray sum, especially when there are no constraints on subarray length or when negative values are allowed.

• Example:

  • Given an array, find the maximum sum of any subarray.

---

3) Prefix Sum & HashMap:

• When to Use:

  • Modulo arithmetic (e.g., sum divisible by a number).
  • Checking sums over subarrays (especially when the subarray can be of any size).

• Why It Works:

  • The prefix sum allows us to break down a subarray sum into differences between two prefix sums.
  • HashMaps are used for fast lookups of previously seen sums, especially useful for problems with conditions like "sum divisible by k."

• Common Problem Types:

  • Finding subarrays that sum to k, or removing a subarray to make a sum divisible by a given value.

• Example:

  • Find the smallest subarray whose sum is divisible by a number p.

---

4. Practice Questions

Easy Problems:

1. Assign Cookies
2. Buy Two Chocolates
3. Count Elements with Maximum Frequency
4. Divide Array into Arrays with Max Difference
5. Find Common Characters
6. Lemonade Change
7. Minimum Common Value

---

Two-Pointer Problems:

1. 3Sum
2. 3Sum Closest
3. Longest Mountain in Array
4. Maximum Erasure Value
5. Max Consecutive Ones II

---

Prefix Sum Problems:

1. Contiguous Array
2. Continuous Subarray Sum
3. Count Number of Nice Subarrays
4. Find Pivot Index
5. K-radius Subarray Averages

---

5. Let's Solve Some Problems:

Leetcode Problems:

1. Container With Most Water
2. Maximum Product Subarray
3. Subarray Sum Equals K
4. Count Number of Nice Subarrays

OA Problem:

1. LinkedIn - SDE Intern:

   • Question: Given a list of words, if any two adjacent characters in a word are equal, change one of them. Determine the minimum number of substitutions so the final string contains no adjacent equal characters.

   Example:
   Input: ['add', 'boook', 'break']
   Output: [1, 1, 0]

---