Level 1 Array & String Problems in C++

Solving Counting Problems Using Multiple Approaches

When learning problem-solving, counting problems are the foundation.
Instead of solving them in only one way, I tried multiple approaches:

1. Normal looping
2. Frequency arrays
3. unordered_map

This article covers Level-1 counting problems, how to solve them, and when to use which approach.

🟢 Problem Set (Level 1)

Count frequency of each element in an array
Count even and odd numbers
Count positive, negative, and zero elements
Count characters in a string
Check if all elements are unique

1️⃣ Count Frequency of Each Element
Approach 1: Using unordered_map

unordered_map<int, int> freq;
for (int x : arr) {
    freq[x]++;
}

Time: O(n) average
Space: O(n)

✔ Best when range is large or unknown
✔ Interview-preferred

Approach 2: Frequency Array

int freq[1001] = {0};
for (int x : arr) {
    freq[x]++;
}

Time: O(n)
Space: O(k) (range size)

✔ Very fast
❌ Only works when range is small & known

Approach 3: Normal Nested Loop

for (int i = 0; i < n; i++) {
    int count = 0;
    for (int j = 0; j < n; j++) {
        if (arr[i] == arr[j]) count++;
    }
}

Time: O(n²)
Space: O(1)

❌ Not efficient
✔ Useful to explain logic in interviews

2️⃣ Count Even and Odd Numbers

Normal Approach

int even = 0, odd = 0;
for (int x : arr) {
    if (x % 2 == 0) even++;
    else odd++;
}

Time: O(n)
Space: O(1)

✔ Best possible solution

3️⃣ Count Positive, Negative, and Zero Elements

int pos = 0, neg = 0, zero = 0;
for (int x : arr) {
    if (x > 0) pos++;
    else if (x < 0) neg++;
    else zero++;
}

Time: O(n)
Space: O(1)

✔ Simple greedy counting
✔ No extra memory

4️⃣ Count Characters in a String

Using unordered_map

unordered_map<char, int> freq;
for (char c : s) {
    freq[c]++;
}

Time: O(n)
Space: O(1) (since char set is limited)

Using Frequency Array

int freq[256] = {0};
for (char c : s) {
    freq[c]++;
}

✔ Faster
✔ Predictable memory

5️⃣ Check If All Elements Are Unique

Using unordered_set

unordered_set<int> s;
for (int x : arr) {
    if (s.count(x)) return false;
    s.insert(x);
}
return true;

Time: O(n) average
Space: O(n)

Using Nested Loop (No Extra Space)

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] == arr[j]) return false;
    }
}
return true;

Time: O(n²)
Space: O(1)

🔍 Comparison Summary

Problem Type --- Best Approach
Large range --- unordered_map
Small range --- Frequency array
No space allowed --- Nested loops
Just counting --- Normal loop

🧠 Key Learning

One problem can have multiple correct solutions. The best solution depends on constraints. STL simplifies code but logic still matters

🎯 Interview Takeaway

Interviewers don’t just want the answer.
They want to know:

Why you chose this approach
What the complexity is
What alternatives exist

Learning problems this way builds strong fundamentals.