Sort Characters By Frequency

🎯

Sort Characters By Frequency

mediumHEAPAmazonFacebookGoogle

Imagine you want to display the most popular letters first in a word cloud, sorted by how often they appear.

💡 This problem is about counting how often each character appears and then sorting characters by their frequency. Beginners often struggle because they try to sort characters directly without counting frequencies first, or they don't know how to efficiently sort by frequency.

📋

Problem Statement

Given a string s, sort it in decreasing order based on the frequency of characters. Return the sorted string. Characters with higher frequency should appear before those with lower frequency.

1 ≤ s.length ≤ 10^5s consists of ASCII characters.

💡

Example

Input"tree"

Outputeert

The character 'e' appears twice, so it should come before 'r' and 't' which appear once each.

• All characters are unique → output can be any permutation of input
• All characters are the same → output is the same string
• Empty string → output is empty string
• String with multiple characters having same frequency → order among them does not matter

⚠️

Common Mistakes

Sorting characters directly without counting frequency

Output is sorted lexicographically, not by frequency

✅ Count frequencies first, then sort by frequency

Using min heap instead of max heap without negating counts

Characters with lowest frequency come first, wrong order

✅ Use max heap or negate counts when using min heap implementations

Not handling empty string input

Code may throw error or return null

✅ Check for empty input and return empty string early

Appending characters incorrectly (e.g., appending count instead of repeating character count times)

Output string has wrong characters or length

✅ Use string repetition methods or loops to append character count times

Using sorting on entire string instead of unique characters

Unnecessary overhead, slower performance

✅ Sort only unique characters by frequency, not the whole string

🧠

Brute Force (Frequency Counting + Sorting by Frequency)

💡 This approach introduces the core idea of counting frequencies and sorting characters by frequency. It is simple and intuitive but not the most efficient for very large inputs.

Intuition

Count how many times each character appears, then sort all characters based on these counts in descending order, and finally build the output string accordingly.

Algorithm

1. Count frequency of each character using a hash map.
2. Sort characters based on frequency in descending order.
3. Build the result string by repeating each character frequency times.
4. Return the constructed string.

💡 The main challenge is to realize that sorting by frequency is the key step, and building the string after sorting is straightforward.

</>

Code

from collections import Counter

def frequencySort(s: str) -> str:
    freq = Counter(s)  # Count frequency of each character
    # Sort characters by frequency descending
    sorted_chars = sorted(freq.items(), key=lambda x: x[1], reverse=True)
    result = []
    for char, count in sorted_chars:
        result.append(char * count)  # Append character count times
    return ''.join(result)

# Driver code
if __name__ == '__main__':
    test = "tree"
    print(frequencySort(test))  # Expected: eert or eetr

Line Notes

freq = Counter(s)Count frequency of each character in the string to know how many times each appears

sorted(freq.items(), key=lambda x: x[1], reverse=True)Sort characters by their frequency in descending order to prioritize higher frequency first

result.append(char * count)Add the character repeated count times to the result list to build the output string correctly

return ''.join(result)Join all parts to form the final string to return the sorted string by frequency

import java.util.*;

public class Solution {
    public static String frequencySort(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1); // Count frequency
        }
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(freq.entrySet());
        list.sort((a, b) -> b.getValue() - a.getValue()); // Sort descending
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            for (int i = 0; i < entry.getValue(); i++) {
                sb.append(entry.getKey()); // Append character count times
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String test = "tree";
        System.out.println(frequencySort(test)); // Expected: eert or eetr
    }
}

Line Notes

freq.put(c, freq.getOrDefault(c, 0) + 1)Count frequency of each character in the string to track occurrences

list.sort((a, b) -> b.getValue() - a.getValue())Sort entries by frequency descending to order characters by count

for (int i = 0; i < entry.getValue(); i++)Append character repeated count times to build the output string correctly

return sb.toString()Return the final constructed string after building it

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

string frequencySort(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++; // Count frequency
    }
    vector<pair<char, int>> vec(freq.begin(), freq.end());
    sort(vec.begin(), vec.end(), [](auto &a, auto &b) {
        return a.second > b.second; // Sort descending
    });
    string result;
    for (auto &p : vec) {
        result.append(p.second, p.first); // Append character count times
    }
    return result;
}

int main() {
    string test = "tree";
    cout << frequencySort(test) << endl; // Expected: eert or eetr
    return 0;
}

Line Notes

freq[c]++Count frequency of each character in the string to know counts

sort(vec.begin(), vec.end(), [](auto &a, auto &b)Sort vector by frequency descending to prioritize higher frequency characters

result.append(p.second, p.first)Append character repeated count times to build the output string

return resultReturn the final constructed string after building

function frequencySort(s) {
    const freq = new Map();
    for (const c of s) {
        freq.set(c, (freq.get(c) || 0) + 1); // Count frequency
    }
    const arr = Array.from(freq.entries());
    arr.sort((a, b) => b[1] - a[1]); // Sort descending
    let result = '';
    for (const [char, count] of arr) {
        result += char.repeat(count); // Append character count times
    }
    return result;
}

// Driver code
console.log(frequencySort("tree")); // Expected: eert or eetr

Line Notes

freq.set(c, (freq.get(c) || 0) + 1)Count frequency of each character in the string to track occurrences

arr.sort((a, b) => b[1] - a[1])Sort array by frequency descending to order characters by count

result += char.repeat(count)Append character repeated count times to build the output string

return resultReturn the final constructed string after building

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Counting frequencies takes O(n). Sorting characters by frequency takes O(k log k), where k is number of unique chars, up to O(n). Building the output is O(n). Overall O(n log n).

💡 For n=100000, sorting can be expensive but still feasible; this approach is straightforward but not optimal.

Interview Verdict: Accepted

This approach works well for moderate input sizes and is easy to implement, making it a good first solution.

🧠

Better (Max Heap / Priority Queue)

💡 Using a max heap to always extract the character with the highest frequency avoids sorting all characters at once and can be more efficient when frequencies vary widely.

Intuition

Count frequencies, then push all characters into a max heap keyed by frequency. Pop from the heap to build the output string in order of highest frequency first.

Algorithm

1. Count frequency of each character using a hash map.
2. Push all characters with their frequencies into a max heap.
3. While heap is not empty, pop the top element and append the character frequency times to the result.
4. Return the constructed string.

💡 The heap ensures we always pick the character with the highest frequency next, avoiding full sorting.

</>

Code

from collections import Counter
import heapq

def frequencySort(s: str) -> str:
    freq = Counter(s)
    max_heap = [(-count, char) for char, count in freq.items()]  # Use negative count for max heap
    heapq.heapify(max_heap)
    result = []
    while max_heap:
        count, char = heapq.heappop(max_heap)
        result.append(char * (-count))  # Append char count times
    return ''.join(result)

# Driver code
if __name__ == '__main__':
    test = "tree"
    print(frequencySort(test))  # Expected: eert or eetr

Line Notes

max_heap = [(-count, char) for char, count in freq.items()]Create max heap by negating counts because Python's heapq is a min heap; negation flips order

heapq.heapify(max_heap)Transform list into a heap in O(k) time to prepare for efficient extraction

count, char = heapq.heappop(max_heap)Pop character with highest frequency (lowest negative count) to get next most frequent

result.append(char * (-count))Append character repeated frequency times to result to build output string

import java.util.*;

public class Solution {
    public static String frequencySort(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        maxHeap.addAll(freq.entrySet());
        StringBuilder sb = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> entry = maxHeap.poll();
            for (int i = 0; i < entry.getValue(); i++) {
                sb.append(entry.getKey());
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String test = "tree";
        System.out.println(frequencySort(test)); // Expected: eert or eetr
    }
}

Line Notes

PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue())Create max heap based on frequency descending to always extract highest frequency

maxHeap.addAll(freq.entrySet())Add all character-frequency pairs to the heap for processing

Map.Entry<Character, Integer> entry = maxHeap.poll()Extract character with highest frequency to append next

for (int i = 0; i < entry.getValue(); i++)Append character repeated frequency times to build output string

#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>

using namespace std;

string frequencySort(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    auto cmp = [](pair<char,int> &a, pair<char,int> &b) { return a.second < b.second; };
    priority_queue<pair<char,int>, vector<pair<char,int>>, decltype(cmp)> maxHeap(cmp);
    for (auto &p : freq) {
        maxHeap.push(p);
    }
    string result;
    while (!maxHeap.empty()) {
        auto p = maxHeap.top(); maxHeap.pop();
        result.append(p.second, p.first);
    }
    return result;
}

int main() {
    string test = "tree";
    cout << frequencySort(test) << endl; // Expected: eert or eetr
    return 0;
}

Line Notes

auto cmp = [](pair<char,int> &a, pair<char,int> &b) { return a.second < b.second; }Comparator for max heap based on frequency descending to prioritize higher frequency

priority_queue<pair<char,int>, vector<pair<char,int>>, decltype(cmp)> maxHeap(cmp)Declare max heap with custom comparator for frequency ordering

maxHeap.push(p)Push character-frequency pair into heap for processing

result.append(p.second, p.first)Append character repeated frequency times to build output string

function frequencySort(s) {
    const freq = new Map();
    for (const c of s) {
        freq.set(c, (freq.get(c) || 0) + 1);
    }
    const maxHeap = [];
    for (const [char, count] of freq.entries()) {
        maxHeap.push({char, count});
    }
    maxHeap.sort((a, b) => b.count - a.count); // Simulate max heap by sorting
    let result = '';
    while (maxHeap.length > 0) {
        const {char, count} = maxHeap.shift();
        result += char.repeat(count);
    }
    return result;
}

// Driver code
console.log(frequencySort("tree")); // Expected: eert or eetr

Line Notes

freq.set(c, (freq.get(c) || 0) + 1)Count frequency of each character to track occurrences

maxHeap.push({char, count})Add character-frequency pair to array for processing

maxHeap.sort((a, b) => b.count - a.count)Sort array descending by frequency to simulate max heap behavior

result += char.repeat(count)Append character repeated frequency times to build output string

⏱

Complexity

TimeO(n + k log k)

SpaceO(n)

Counting frequencies is O(n). Building the heap is O(k). Each pop is O(log k), total O(k log k). Building output is O(n). Overall O(n + k log k), better than sorting all characters if k << n.

💡 For large strings with few unique characters, this approach is more efficient than full sorting.

Interview Verdict: Accepted

This approach is more scalable and preferred when the number of unique characters is much smaller than string length.

🧠

Optimal (Bucket Sort by Frequency)

💡 Bucket sort leverages the fact that frequency ranges from 1 to n, allowing us to group characters by frequency and then output from highest frequency bucket to lowest without sorting keys explicitly.

Intuition

Count frequencies, then create buckets where index represents frequency. Place characters into buckets by their frequency. Finally, iterate buckets from high to low frequency to build the result.

Algorithm

1. Count frequency of each character using a hash map.
2. Create an array of buckets where index is frequency, each bucket holds characters with that frequency.
3. Place each character into the bucket corresponding to its frequency.
4. Iterate buckets from highest frequency to lowest, appending characters repeated frequency times to the result.
5. Return the constructed string.

💡 This approach avoids sorting by using frequency as direct index, making it very efficient.

</>

Code

from collections import Counter

def frequencySort(s: str) -> str:
    freq = Counter(s)
    max_freq = max(freq.values(), default=0)
    buckets = [[] for _ in range(max_freq + 1)]
    for char, count in freq.items():
        buckets[count].append(char)  # Place char in bucket of its frequency
    result = []
    for freq_count in range(max_freq, 0, -1):
        for char in buckets[freq_count]:
            result.append(char * freq_count)  # Append char repeated freq_count times
    return ''.join(result)

# Driver code
if __name__ == '__main__':
    test = "tree"
    print(frequencySort(test))  # Expected: eert or eetr

Line Notes

max_freq = max(freq.values(), default=0)Find maximum frequency to size buckets array appropriately

buckets = [[] for _ in range(max_freq + 1)]Create buckets indexed by frequency to group characters efficiently

buckets[count].append(char)Place character in bucket corresponding to its frequency for grouping

for freq_count in range(max_freq, 0, -1)Iterate buckets from highest frequency down to 1 to build output in correct order

import java.util.*;

public class Solution {
    public static String frequencySort(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        int maxFreq = 0;
        for (int count : freq.values()) {
            maxFreq = Math.max(maxFreq, count);
        }
        List<Character>[] buckets = new List[maxFreq + 1];
        for (int i = 0; i <= maxFreq; i++) {
            buckets[i] = new ArrayList<>();
        }
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            buckets[entry.getValue()].add(entry.getKey());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = maxFreq; i > 0; i--) {
            for (char c : buckets[i]) {
                for (int j = 0; j < i; j++) {
                    sb.append(c);
                }
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String test = "tree";
        System.out.println(frequencySort(test)); // Expected: eert or eetr
    }
}

Line Notes

int maxFreq = 0;Initialize max frequency variable to track highest count

buckets = new List[maxFreq + 1];Create array of buckets indexed by frequency for grouping characters

buckets[entry.getValue()].add(entry.getKey());Add character to bucket corresponding to its frequency for grouping

for (int i = maxFreq; i > 0; i--)Iterate buckets from highest frequency down to 1 to build output string in order

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

string frequencySort(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    int maxFreq = 0;
    for (auto &p : freq) {
        maxFreq = max(maxFreq, p.second);
    }
    vector<vector<char>> buckets(maxFreq + 1);
    for (auto &p : freq) {
        buckets[p.second].push_back(p.first);
    }
    string result;
    for (int i = maxFreq; i > 0; i--) {
        for (char c : buckets[i]) {
            result.append(i, c);
        }
    }
    return result;
}

int main() {
    string test = "tree";
    cout << frequencySort(test) << endl; // Expected: eert or eetr
    return 0;
}

Line Notes

int maxFreq = 0;Track maximum frequency to size buckets array correctly

vector<vector<char>> buckets(maxFreq + 1);Create buckets indexed by frequency to group characters efficiently

buckets[p.second].push_back(p.first);Add character to bucket for its frequency to group characters

for (int i = maxFreq; i > 0; i--)Iterate buckets from highest frequency down to 1 to build output string in order

function frequencySort(s) {
    const freq = new Map();
    for (const c of s) {
        freq.set(c, (freq.get(c) || 0) + 1);
    }
    let maxFreq = 0;
    for (const count of freq.values()) {
        maxFreq = Math.max(maxFreq, count);
    }
    const buckets = Array.from({length: maxFreq + 1}, () => []);
    for (const [char, count] of freq.entries()) {
        buckets[count].push(char);
    }
    let result = '';
    for (let i = maxFreq; i > 0; i--) {
        for (const char of buckets[i]) {
            result += char.repeat(i);
        }
    }
    return result;
}

// Driver code
console.log(frequencySort("tree")); // Expected: eert or eetr

Line Notes

maxFreq = Math.max(maxFreq, count)Find maximum frequency to size buckets array correctly

const buckets = Array.from({length: maxFreq + 1}, () => [])Create buckets indexed by frequency to group characters efficiently

buckets[count].push(char)Add character to bucket for its frequency to group characters

for (let i = maxFreq; i > 0; i--)Iterate buckets from highest frequency down to 1 to build output string in order

⏱

Complexity

TimeO(n)

SpaceO(n)

Counting frequencies is O(n). Buckets array size is at most n. Placing characters into buckets is O(k), building output is O(n). No sorting needed, so overall linear time.

💡 This approach is optimal for large inputs because it avoids sorting and uses direct indexing.

Interview Verdict: Accepted

This is the most efficient approach and preferred in interviews when frequency range is manageable.

📊

All Approaches - One-Glance Tradeoffs

💡 Bucket sort is optimal and preferred in interviews; heap is a good intermediate step; brute force sorting is simplest but less efficient.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n log n)	O(n)	No	Yes	Mention only - easy to implement but not optimal
2. Max Heap	O(n + k log k)	O(n)	No	Yes	Good intermediate approach, shows knowledge of heaps
3. Bucket Sort	O(n)	O(n)	No	Yes	Optimal approach, best to code if comfortable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach: count frequencies and sort characters by frequency.Discuss the limitations of sorting and introduce the max heap approach.Explain the bucket sort approach as the optimal solution.Write clean code for the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to count frequencies, choose appropriate data structures (heap, buckets), optimize time complexity, and handle edge cases.

Common Follow-ups

• What if characters are Unicode? → Use a hash map for frequency counting.
• Can you do this in O(n) time? → Yes, using bucket sort approach.

💡 Follow-ups often test your knowledge of data structures and ability to optimize beyond sorting.

🔍

Pattern Recognition

When to Use

1) Need to sort or select elements by frequency or count; 2) Input involves characters or elements with duplicates; 3) Output requires ordering by frequency; 4) Constraints allow frequency counting and sorting or bucket sort.

Signature Phrases

sort characters by frequencyreturn string sorted by frequency

NOT This Pattern When

Sorting strings lexicographically or substring problems without frequency constraints

Similar Problems

Top K Frequent Elements - similar frequency counting and heap usageSort Characters By Frequency II - variant with additional constraintsRearrange String k Distance Apart - frequency and heap with distance constraints

Practice

1. Consider the following Python code implementing a frequency stack using a max-heap with timestamp. After executing the sequence of operations below, what is the output of the last pop() call?

fs = FreqStack()
fs.push(1)
fs.push(2)
fs.push(1)
print(fs.pop())
print(fs.pop())

easy

A. 1 and then 1

B. 2 and then 1

C. 1 and then 2

D. 2 and then 2

Solution

1. Step 1: Trace push operations

   Push 1: freq[1]=1, time=1, heap push (-1, -1, 1) Push 2: freq[2]=1, time=2, heap push (-1, -2, 2) Push 1: freq[1]=2, time=3, heap push (-2, -3, 1)

2. Step 2: Trace pop operations

   First pop: heap pops (-2, -3, 1) -> returns 1, freq[1]=1 Second pop: heap now has (-1, -2, 2) and (-1, -1, 1). Max freq is 1, tie broken by time: -2 > -1, so pop (-1, -2, 2) returns 2.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Most frequent element 1 popped first, then next most recent with freq 1 is 2 [OK]

Hint: Most frequent and most recent element pops first [OK]

Common Mistakes:

• Ignoring timestamp order in heap
• Mixing up pop order when frequencies tie

2. You need to continuously track the kth largest element in a stream of integers where new elements arrive one by one. Which approach guarantees efficient updates and retrievals after each new element arrives?

easy

A. Sort the entire stream after each new element and pick the kth largest element.

B. Maintain a min-heap of size k containing the current k largest elements seen so far.

C. Use a max-heap containing all elements and extract the kth largest by popping k times.

D. Use dynamic programming to store intermediate kth largest values for all prefixes.

Solution

1. Step 1: Understand the problem constraints

   We need to efficiently update and retrieve the kth largest element after each insertion in a stream.

2. Step 2: Evaluate approaches

   Sorting the entire stream each time (B) is inefficient (O(n log n) per add). Using a max-heap of all elements (C) requires popping k times per query, which is costly. Dynamic programming (D) is not applicable here as the problem is not about overlapping subproblems but about maintaining order dynamically. Maintaining a min-heap of size k (A) keeps the kth largest element at the root, allowing O(log k) updates and O(1) retrieval.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap of size k efficiently tracks kth largest element [OK]

Hint: Min-heap size k keeps kth largest at root efficiently [OK]

Common Mistakes:

• Sorting entire stream each time is too slow
• Using max-heap of all elements wastes space and time
• Dynamic programming is irrelevant here

3. You are given a 2D matrix and need to find the kth largest value among all XOR coordinate values, where each coordinate value is the XOR of all elements from the top-left corner to that coordinate. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use nested loops to compute XOR for each coordinate independently, then sort all values.

B. Apply dynamic programming with memoization to store XOR values and then sort them.

C. Use a greedy approach to pick the largest elements first and XOR them until k values are found.

D. Compute a prefix XOR matrix and maintain a min-heap of size k to track the kth largest value.

Solution

1. Step 1: Understand the problem constraints

   Computing XOR values for each coordinate independently with nested loops leads to O(m^2 * n^2) time, which is inefficient.

2. Step 2: Recognize prefix XOR and min-heap usage

   Using a prefix XOR matrix allows O(m * n) computation of all XOR coordinate values. Maintaining a min-heap of size k ensures we track the kth largest value efficiently, leading to O(m * n * log k) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix XOR + min-heap is optimal for kth largest XOR coordinate value [OK]

Hint: Prefix XOR + min-heap is optimal for kth largest XOR values [OK]

Common Mistakes:

• Thinking nested loops with sorting is efficient enough
• Assuming greedy selection works for XOR
• Confusing DP with prefix XOR usage

4. You are given a list of words and need to find the top k words that appear most frequently, with ties broken by lexicographical order. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Sort all unique words by frequency descending and lex order ascending, then pick top k

B. Use a dynamic programming approach to count frequencies and select top k

C. Use a greedy approach by repeatedly picking the most frequent word until k are chosen

D. Use bucket sort by frequency, then sort words lexicographically within each bucket, and collect top k

Solution

1. Step 1: Understand frequency distribution

   Counting frequencies is straightforward, but sorting all words fully costs O(n log n).

2. Step 2: Use bucket sort to group words by frequency

   Bucket sort groups words by frequency in O(n), then sorting lex order within buckets is efficient since buckets are smaller.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bucket sort + lex sort within buckets achieves O(n) time [OK]

Hint: Bucket sort by frequency then lex sort is optimal [OK]

Common Mistakes:

• Assuming full sort is optimal
• Using DP for frequency counting
• Greedy without sorting fails tie-break

5. What is the time complexity of the optimal binary search on value range approach to find the kth smallest element in an n x n sorted matrix, where the matrix elements range between min and max values?

medium

A. O(n^2 log n)

B. O(n log(max - min))

C. O(n^2 log(max - min))

D. O(n log n)

Solution

1. Step 1: Identify binary search iterations

   Binary search on value range performs O(log(max - min)) iterations.

2. Step 2: Analyze countLessEqual complexity

   Counting elements ≤ mid takes O(n) time by traversing from bottom-left to top-right.

3. Step 3: Combine complexities

   Total time is O(n * log(max - min)). However, since n is matrix dimension, counting is O(n), but matrix size is n², so counting is O(n) per iteration, total O(n log(max-min)).

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Counting is O(n), binary search O(log(max-min)) [OK]

Hint: Counting ≤ mid is O(n), not O(n²) [OK]

Common Mistakes:

• Confusing n with n² in counting
• Assuming sorting complexity applies