DAY 15 Wrapping Up with Advanced Array Challenges

Hello Everyone!

I’m Somuya Khandelwal, back with the updates from Day 5 of Week 3 in my competitive programming journey. Today, I worked on Array-based problems that tested my ability to efficiently traverse arrays and handle tricky edge cases. These problems pushed me to think critically about optimization and provided a great way to wrap up the week.

---

What I Worked On Today

1. H-Index (Medium Difficulty)

   • Task: Determine the H-Index of a researcher based on their citation counts.
   • Approach:
     • First, I sorted the citations in descending order and checked for the largest value where citation[i] >= i + 1.
     • I also explored a more optimized approach using counting sort principles for larger datasets.
   • What I Learned:
     • Sorting is a straightforward way to simplify problems like these, but it’s not always the most efficient.
     • The relationship between the values and indices in the array is crucial to solve problems like this effectively.

2. Gas Station (Medium Difficulty)

   • Task: Determine if it’s possible to complete a circular route starting and ending at the same gas station.
   • Approach:
     • Calculated the net gas at each station and ensured the total gas was non-negative.
     • Used a greedy method to identify the starting station, resetting the starting point whenever the cumulative gas went below zero.
   • What I Learned:
     • Circular problems often seem complicated but can be tackled effectively with greedy strategies.
     • The concept of resetting when conditions fail helped me break the problem into manageable subproblems.

---

What I Learned Today

1. Balancing Simplicity and Optimization:

   • The H-Index problem showed how sorting simplifies logic, but also opened my eyes to more optimized approaches for larger inputs.

2. Greedy Algorithms in Circular Problems:

   • The Gas Station problem highlighted how local optimizations, like resetting the starting point, lead to an efficient global solution.

3. Analyzing Problem Constraints:

   • Careful consideration of constraints, like ensuring the total gas is non-negative, made tackling these problems easier.

4. Testing for Edge Cases:

   • Scenarios like empty citation arrays in H-Index or insufficient gas in Gas Station reminded me of the importance of covering all edge cases.

---

Reflections and Challenges

The Gas Station problem was the most interesting challenge of the day. Understanding how local gas deficits impacted the global solution required a bit of trial and error before I got the logic right. Once I figured out the reset logic, the solution felt much more intuitive. For the H-Index, implementing both a basic sorting approach and a more optimized method was a great way to compare different strategies and see the trade-offs between simplicity and performance.

---

Looking Ahead

With Week 3 officially complete, I’m excited to plan for Week 4, where I’ll dive into Graph Algorithms, Greedy Problems, and 2D Dynamic Programming. These topics will challenge me even more and help me further improve my problem-solving skills.

Thank you for following along with my journey! Stay tuned for more updates as I continue learning, solving, and growing in the exciting world of competitive programming.

Best,

Somuya