DEV Community

Ertugrul
Ertugrul

Posted on • Edited on

🗓 Daily LeetCode Progress – Day 3

Problems Solved:

  • #347 Top K Frequent Elements
  • #238 Product of Array Except Self

This continues my daily series (Day X: String Hashing/Sorting patterns). Today I focused on array hashing/bucket sort and prefix/suffix product patterns, implementing both Python and C++ solutions.

💡 What I Learned

Today’s focus was on classic frequency counting and prefix-suffix tricks.

Key takeaways:

  • Python: Leveraging Counter.most_common(k) for concise frequency extraction.
  • C++: Practiced implementing bucket sort manually to avoid O(n log n) sorting, and applied two-pass prefix/suffix accumulation for product problems.
  • Learned to avoid pitfalls like misusing reserve vs. resize in vectors and off-by-one errors in reverse loops.

🧩 #347 — Top K Frequent Elements

Python (Counter) 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        result = []
        freq = Counter(nums)
        for i, count in freq.most_common(k):
            result.append(i)
        return result
Enter fullscreen mode Exit fullscreen mode

Why it works: Counter directly provides frequencies; most_common(k) sorts them by frequency.

Time: O(n log n) (due to sorting inside most_common).
Space: O(n).

C++ (Bucket Sort) 

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> freq;
        freq.reserve(nums.size()*2);
        for (int x : nums){
            freq[x]++;
        }

        int n = nums.size();
        vector<vector<int>> buckets(n+1);
        for (const auto& [val,f]: freq){
            buckets[f].push_back(val);
        }

        vector<int> res;
        res.reserve(k);
        for (int f = n; f >= 1 && (int)res.size() < k; --f){
            for (int val : buckets[f]){
                res.push_back(val);
                if ((int)res.size() == k) break;
            }
        }
        return res;
    }
};
Enter fullscreen mode Exit fullscreen mode

Why it works: Frequency max is at most n; bucket sort avoids full sorting.

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

🧩 #238 — Product of Array Except Self

Python (Prefix + Suffix) 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n

        left = 1
        for i in range(n):
            ans[i] = left
            left *= nums[i]

        right = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= right
            right *= nums[i]

        return ans
Enter fullscreen mode Exit fullscreen mode

Why it works: First pass builds prefix products; second pass multiplies suffix products in place.

Time: O(n)
Space: O(1) extra (output array excluded)

C++ (Prefix + Suffix) 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        int left = 1, right = 1;
        vector<int> ans(n, 1);

        for(int i = 0; i < n; i++){
            ans[i] *= left;
            left *= nums[i];
        }

        for(int i = n-1; i >= 0; i--){
            ans[i] *= right;
            right *= nums[i];
        }

        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode

Why it works: Same two-pass idea, with careful use of ans as storage.

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

📸 Achievements

  • Top K Frequent Elements (Python & C++):

Top K python

Top K cpp

  • Product of Array Except Self (Python & C++):

Product python

Product cpp

📦 Complexity Recap

  • Top K Frequent Elements: O(n log n) (Python Counter) vs. O(n) (C++ bucket)
  • Product of Array Except Self: O(n) in both

📣 Join the Journey

I’m solving and documenting problems daily in both Python and C++, highlighting patterns and trade-offs. Follow along if you’re into algorithms and performance tuning.

Links

Top comments (0)