Day 2: Conquering Three Questions in Array — My 100-Day Journey

Introduction

Hey, fellow coders! 👋 Today marks second day of my 100-day coding challenge. In this post, I’ll share my journey of conquering three coding challenges and dive into the intricacies of Arrays. Let’s dive in!

Day 2

Coding Challenges

Challenge 1: Maximum Product Subarray

Maximum Product Subarray (LeetCode)

Solution 1

Finding the optimal approach was a real challenge. While I quickly came up with a brute-force solution, the real difficulty began afterward. I spent an hour brainstorming for a better approach but had no luck. Seeking guidance, I turned to the discussion tab on LeetCode and found a comment that simply said, “Highly non-intuitive” It was a confidence boost.

Navigating YouTube, I stumbled upon Striver’s video addressing this question, presenting two distinct approaches:

1. Modified Kadane’s Algorithm: Referred to in the aforementioned comment, Striver labeled this approach as one that is typically encountered through rote memorization. Preferring to enhance my problem-solving skills rather than relying on memorization, I opted not to pursue this method.
2. Observation-Based Approach: While I won’t delve into the details here, you can refer to Striver’s video for a comprehensive understanding of this alternative approach.

int maxProduct(vector < int > & nums) {
  int max = INT_MIN, prefix = 1, suffix = 1, n = nums.size();
  for (int i = 0; i < n; i++) {
    suffix = suffix == 0 ? 1 : suffix;
    prefix = prefix == 0 ? 1 : prefix;
    prefix *= nums[i];
    suffix *= nums[n - 1 - i];
    max = max > suffix ? max : suffix;
    max = max > prefix ? max : prefix;
  }
  return max;
}

Boosted by renewed confidence, I seamlessly transitioned to the next problem.

Challenge 2: Majority Element II

Majority Element II (LeetCode)

Solution 2

For this question, a straightforward approach involves utilizing a HashMap, offering O(n) time complexity and O(n) space complexity. However, for further optimization, a modified version of Moore’s Voting algorithm can be employed. The intuition behind this is that a maximum of two elements can be the output for this problem. Therefore, the goal is to calculate the two most occurring numbers efficiently.

vector < int > majorityElement(vector < int > & nums) {
    int count1 = 0, count2 = 0, el1 = INT_MIN, el2 = INT_MAX;
    for (auto i: nums) {
        if (count1 == 0 && el2 != i) {
            el1 = i;
            count1 = 1;
        } else if (count2 == 0 && el1 != i) {
            el2 = i;
            count2 = 1;
        } else if (i == el1) {
            count1++;
        } else if (i == el2) {
            count2++;
        } else {
            count1--;
            count2--;
        }
    }
    int c1 = 0, c2 = 0;
    for (auto i: nums) {
        if (i == el1)
            c1++;
        else if (i == el2)
            c2++;
    }
    int th = nums.size() / 3;
    vector < int > out;
    if (c1 > th)
        out.push_back(el1);
    if (c2 > th)
        out.push_back(el2);
    return out;
}

Challenge 3: Max Chunks To Make Sorted

Max Chunks To Make Sorted (Leetcode)

Solution 3

Approach that I took for this problem was based on observation that I made. So observation is simple. We can make a chunk of prefix if and only if all the elements on left are less than or equal to index of that element. Just converted that approach to code and we were done.

int maxChunksToSorted(vector < int > & arr) {
    int b = INT_MIN, c = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (b < arr[i])
            b = arr[i];
        if (b <= i) {
            c++;
        }
    }
    return c;
}

Reflection

Upon reflecting on today’s challenges and solutions, I’ve come to realize that the process of learning a more optimal solution and understanding the thought process behind it is just as crucial, if not more so, than solving the problem itself. It’s tempting to give up when the right solution proves elusive, but the true battle lies in maintaining consistency.

What’s Next?

Stay tuned for Day 3 as I embark on the next leg of my 100-day coding journey. Tomorrow, I’ll delve deeper into Arrays, marking the last day for array questions. Thrilled to share my progress with you all!

Conclusion

Thanks for joining me on this coding adventure. Feel free to share your thoughts and insights in the comments. Happy coding! 🚀

Current Progress