DAY 15 Wrapping Up with Advanced Array Challenges

Hello Everyone!

I am Somuya Khandelwal, back with updates from Day 5 of Week 3 in my competitive programming journey. Today’s focus was on solving Array-based problems that required advanced traversal and optimization techniques. These challenges helped me refine my skills in handling arrays efficiently while tackling edge cases and constraints.

What I Worked On Today

1. H-Index (Medium Difficulty)

   • Calculate the H-Index of a researcher based on their citation counts.
   • Approach:
     • Sorted the array in descending order and found the maximum value where citation[i] >= i + 1.
     • Explored an optimized solution using a counting sort-like approach for larger datasets.
   • What I Learned:
     • Sorting simplifies many problems but can be optimized with more advanced approaches.
     • Understanding the relationship between indices and values in arrays is critical for problems like this.

2. Gas Station (Medium Difficulty)

   • Determine if it’s possible to complete a circular route in a list of gas stations, starting at one station and ending at the same station.
   • Approach:
     • Calculated the net gas at each station and checked if the total gas was non-negative.
     • Used a greedy approach to find the starting station, resetting the starting point whenever the cumulative gas became negative.
   • What I Learned:
     • Problems requiring circular traversals often benefit from greedy algorithms.
     • Resetting and re-evaluating subproblems (e.g., resetting the starting station) is an effective strategy in array-based optimization problems.

What I Learned Today

1. Sorting and Optimization:

   • Problems like H-Index demonstrate how sorting can simplify logic but also highlight opportunities for further optimization.

2. Greedy Techniques in Circular Problems:

   • The Gas Station problem reinforced how greedy algorithms can simplify seemingly complex problems by focusing on local decisions.

3. Understanding Problem Constraints:

   • Both problems required careful analysis of constraints, such as ensuring the gas sum was non-negative in Gas Station or interpreting citation counts in H-Index.

4. Edge Case Handling:

   • Edge cases like empty arrays, zero citations, or routes with insufficient gas emphasized the importance of thorough testing.

Reflections and Challenges

The Gas Station problem was particularly challenging at first because it required understanding the relationship between local and global gas balances. Debugging the starting station reset logic took some effort, but the final solution was efficient and satisfying. The H-Index problem provided a great opportunity to explore both basic sorting and optimized solutions, enhancing my understanding of array traversal techniques.

Looking Ahead

With Week 3 complete, I’m looking forward to planning Week 4, where I’ll focus on Graphs, Greedy Algorithms, and 2D Dynamic Programming. These topics will help me tackle even more complex and exciting problems.

Thank you for following along on my journey! Stay tuned for more updates as I continue to grow and learn in the world of competitive programming.