Blog

first rated contest of the challenge

Two solved, one WA, one lesson that will save me points in every future contest.

Ten days of preparation. Graphs, binary search, sliding window, DP fundamentals. And then contest day arrives and Q1 is about frequency maps and Q2 is about character scoring. Nothing I specifically drilled. Nothing that required any of the patterns I’d been building.

That’s contests for you. They don’t care about your preparation schedule.

Here’s what happened.

Q1 — Limit Occurrences in Sorted Array

Frequency map, filter by limit. Clean solve. ✓ Solved

Q2 — Password Strength

Character scoring with distinct characters. One WA. ✓ Solved (1 WA)

Q3 — Minimum Operations to Sort a Permutation

Had the right instinct, couldn’t close it. (Attempted)

Q4 — Number of Pairs After Increment

Range updates + pair counting. Hard. (Skipped)

Total time on Q1 and Q2: 30 minutes.

Q1 — Limit Occurrences in Sorted Array

Straightforward. Count frequencies, rebuild the array capping each element at k occurrences. I used a map which naturally handles the sorted order. Solved cleanly first try. The follow-up asks for O(1) space in-place — worth thinking about later.

Q2 — Password Strength (and the WA that taught me something)

The problem: score a password based on distinct character types. Lowercase letters score 1, uppercase 2, digits 3, special characters 5. Each character type contributes once regardless of how many times it appears.

My first submission used boolean flags — hasLower, hasUpper, hasNum, hasSpecial — and added points the first time each category appeared. Wrong answer.

The part I misread: each distinct character contributes at most once. Not each character type — each individual character. So if your password has three different lowercase letters, you score 1 + 1 + 1 = 3, not just 1.

The fix was simple: dump the password into a set to get distinct characters, then score each one individually. My boolean approach was solving a completely different problem.

Read the question 3 times. Even if you think you got it.

New rule. Permanent rule. Costs nothing, saves everything.

Q3 — Minimum Operations to Sort a Permutation

My actual incorrect attempt:

class Solution {
public:
    int minOperations(vector<int>& nums) {
        // numbers 0 to n.
        // permutation means randomly arranged.
        // 1. reverse - only useful if the array is reverse sorted I mean non decreasing sorted.
        // 2. rotate by 1 unless its sorted or reverse sorted.
        // first should I find if the array is rotated sorted using binary search.
        // if it is not you can't if it is you can sort it.
        // no but that won't work on 1,0,2.
        // what else can I do?
        // what if i try n-1 rotations at max and check if it gets sorted or reverse sorted?
        // its cool but that would be O(n^2) and constraints can't be done.
        // but n log n would work. either I can make rotations O(log n) or checking sorted property.
        // see in total I can do n-1 rotations right?. what if I do a binary search.
        // let's say I try mid.
        // if it is not sorting the array in either order I'll get the low to mid+1
        // if it does store it as a possiblity and then do high=mid-1
        // is it possible?
        // I do see some complications here its not that straightforward.
        // If let's say 2 rotations didn't sort how can I guarantee that any less than that wont'
    }
};

class Solution {
public:
    int minOperations(vector<int>& nums) {
        // numbers 0 to n.
        // permutation means randomly arranged.
        // 1. reverse - only useful if the array is reverse sorted I mean non decreasing sorted.
        // 2. rotate by 1 unless its sorted or reverse sorted.
        // first should I find if the array is rotated sorted using binary search.
        // if it is not you can't if it is you can sort it.
        // no but that won't work on 1,0,2.
        // what else can I do?
        // what if i try n-1 rotations at max and check if it gets sorted or reverse sorted?
        // its cool but that would be O(n^2) and constraints can't be done.
        // but n log n would work. either I can make rotations O(log n) or checking sorted property.
        // see in total I can do n-1 rotations right?. what if I do a binary search.
        // let's say I try mid.
        // if it is not sorting the array in either order I'll get the low to mid+1
        // if it does store it as a possiblity and then do high=mid-1
        // is it possible?
        // I do see some complications here its not that straightforward.
        // If let's say 2 rotations didn't sort how can I guarantee that any less than that wont'
    }
};

I think it’s good, further you decide.

And that’s it for today. Now I’ll solve this one and move ahead with planning the next week.