Module Week 9

Mini-Max Sum

HackerRank

Easy ▼

Source

HackerRank - Mini-Max Sum

Problem

Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two space-separated long integers.

Function Signature

miniMaxSum(arr: List[int]) -> None

Examples

Input: arr = [1, 2, 3, 4, 5]
Output: 10 14
Explanation: The minimum sum is 1+2+3+4 = 10. The maximum sum is 2+3+4+5 = 14.

Input: arr = [7, 69, 2, 221, 8974]
Output: 299 9271

This problem looks tricky at first sight, but is easy if you preprocess the input by sorting it. Once the array is sorted, the minimum sum of four elements and the maximum sum of four elements become obvious.

Sort the array first. After sorting, the four smallest values are at the front and the four largest are at the back. The minimum sum is the sum of the first four elements, and the maximum sum is the sum of the last four elements.

Alternatively, you can compute the total sum of all five elements, then subtract the maximum to get the minimum sum and subtract the minimum to get the maximum sum - no sorting needed at all.

⚙ Knowledge Hub: Searching and Sorting

Sort the array in ascending order
The minimum sum is arr[0] + arr[1] + arr[2] + arr[3] (skip the largest)
The maximum sum is arr[1] + arr[2] + arr[3] + arr[4] (skip the smallest)
Print both values separated by a space

The alternative approach: compute total = sum(arr), then the minimum sum is total - max(arr) and the maximum sum is total - min(arr). This runs in O(n) instead of O(n log n).

def miniMaxSum(arr):
    arr.sort()
    min_sum = sum(arr[:4])
    max_sum = sum(arr[1:])
    print(min_sum, max_sum)

void miniMaxSum(vector<int> arr) {
    sort(arr.begin(), arr.end());
    long min_sum = 0, max_sum = 0;
    for (int i = 0; i < 4; i++) min_sum += arr[i];
    for (int i = 1; i < 5; i++) max_sum += arr[i];
    cout << min_sum << " " << max_sum << endl;
}

static void MiniMaxSum(List<int> arr) {
    arr.Sort();
    long minSum = arr.Take(4).Sum(x => (long)x);
    long maxSum = arr.Skip(1).Sum(x => (long)x);
    Console.WriteLine($"{minSum} {maxSum}");
}

static void miniMaxSum(List<Integer> arr) {
    Collections.sort(arr);
    long minSum = 0, maxSum = 0;
    for (int i = 0; i < 4; i++) minSum += arr.get(i);
    for (int i = 1; i < 5; i++) maxSum += arr.get(i);
    System.out.println(minSum + " " + maxSum);
}

Big Sorting

HackerRank

Easy ▼

Source

HackerRank - Big Sorting

Problem

Consider an array of numeric strings where each string is a positive number with anywhere from 1 to 10⁶ digits. Sort the array's elements in non-decreasing order of their integer values and return the sorted array.

Function Signature

bigSorting(unsorted: List[str]) -> List[str]

Examples

Input: ["31415926535897932384626433832795", "1", "3", "10", "3", "5"]
Output: ["1", "3", "3", "5", "10", "31415926535897932384626433832795"]

Input: ["6", "31415926535897932384626433832795", "1", "3", "10", "3", "5"]
Output: ["1", "3", "3", "5", "6", "10", "31415926535897932384626433832795"]

This is slightly tricky, because some of the test cases use huge strings of digits. Converting to integers for the sort requires a big integer type, and even then you may time out. It is better to work out a way of comparing the strings without needing this conversion.

Write a custom comparator that compares two numeric strings without converting them to integers. The key insight: if two numeric strings have different lengths, the longer one is always larger (because there are no leading zeroes). If they have the same length, a simple lexicographic (dictionary-order) comparison gives the correct numeric ordering.

⚙ Knowledge Hub: Searching and Sorting

Define a comparator that takes two strings a and b
First compare by length: if len(a) != len(b), the shorter string represents the smaller number
If they have the same length, compare them lexicographically (standard string comparison)
Sort the array using this comparator

This works because the input strings have no leading zeroes. Equal-length digit strings sort numerically and lexicographically in the same order.

def bigSorting(unsorted):
    return sorted(unsorted, key=lambda x: (len(x), x))

vector<string> bigSorting(vector<string> unsorted) {
    sort(unsorted.begin(), unsorted.end(),
        [](const string& a, const string& b) {
            if (a.size() != b.size())
                return a.size() < b.size();
            return a < b;
        });
    return unsorted;
}

static List<string> BigSorting(List<string> unsorted) {
    unsorted.Sort((a, b) => {
        if (a.Length != b.Length)
            return a.Length.CompareTo(b.Length);
        return string.Compare(a, b, StringComparison.Ordinal);
    });
    return unsorted;
}

static List<String> bigSorting(List<String> unsorted) {
    unsorted.sort((a, b) -> {
        if (a.length() != b.length())
            return a.length() - b.length();
        return a.compareTo(b);
    });
    return unsorted;
}

Sort Characters by Frequency

LeetCode 451

Medium ▼

Source

LeetCode 451 - Sort Characters by Frequency

Problem

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If there are multiple answers, return any of them.

Function Signature

frequencySort(s: str) -> str

Examples

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice, 'r' and 't' once each. "eetr" is also valid.

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times. "cccaaa" is also valid.

Input: s = "Aabb"
Output: "bbAa"
Explanation: 'b' appears twice, 'A' and 'a' once each. Note 'A' and 'a' are treated as different characters.

This is an exercise in sorting using something other than the value as the sort key. It also includes the very common subtask of counting occurrence frequency, which we have seen many times before.

The output string groups identical characters together, with the most frequent characters appearing first.

Use a dictionary (hash map) to count the frequency of each character, then sort the unique characters by their frequency in descending order. Finally, build the result string by repeating each character according to its count.

⚙ Knowledge Hub: Using Dictionaries ⚙ Knowledge Hub: Counting Frequencies ⚙ Knowledge Hub: Searching and Sorting

Count the frequency of each character using a dictionary
Sort the dictionary entries by frequency in descending order
Build the result by repeating each character by its count

In Python this is a one-liner with Counter and most_common(). In other languages, sort the entries of your frequency map by value descending.

from collections import Counter

def frequencySort(s):
    freq = Counter(s)
    return ''.join(ch * cnt for ch, cnt in freq.most_common())

string frequencySort(string s) {
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    
    vector<pair<char, int>> entries(freq.begin(), freq.end());
    sort(entries.begin(), entries.end(),
        [](auto& a, auto& b) { return a.second > b.second; });
    
    string result;
    for (auto& [ch, cnt] : entries)
        result += string(cnt, ch);
    return result;
}

public string FrequencySort(string s) {
    var freq = new Dictionary<char, int>();
    foreach (char c in s)
        freq[c] = freq.GetValueOrDefault(c) + 1;
    
    var sorted = freq.OrderByDescending(kv => kv.Value);
    var sb = new StringBuilder();
    foreach (var kv in sorted)
        sb.Append(kv.Key, kv.Value);
    return sb.ToString();
}

public String frequencySort(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray())
        freq.merge(c, 1, Integer::sum);
    
    List<Character> chars = new ArrayList<>(freq.keySet());
    chars.sort((a, b) -> freq.get(b) - freq.get(a));
    
    StringBuilder sb = new StringBuilder();
    for (char ch : chars)
        sb.append(String.valueOf(ch).repeat(freq.get(ch)));
    return sb.toString();
}

Top K Frequent Elements

LeetCode 347

Medium ▼

Source

LeetCode 347 - Top K Frequent Elements

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Function Signature

topKFrequent(nums: List[int], k: int) -> List[int]

Examples

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

As with the previous problem, this includes counting occurrence frequencies. You can move from there to the solution using a sort. The challenge task, which is to solve in better than O(n log n) complexity, could use a heap or bucket sort rather than a full sort.

Straightforward approach: count frequencies with a dictionary, sort by frequency descending, and take the first k elements. This is O(n log n).

Faster approach: use a min-heap of size k. After counting frequencies, push each element onto the heap. If the heap exceeds size k, pop the smallest. At the end the heap contains the top k. This is O(n log k).

⚙ Knowledge Hub: Using Dictionaries ⚙ Knowledge Hub: Counting Frequencies ⚙ Knowledge Hub: Searching and Sorting

Count the frequency of each number using a dictionary
Sort approach: sort the unique numbers by their frequency in descending order, return the first k
Heap approach: use a min-heap of size k. For each (number, frequency) pair, push onto the heap. If the heap grows beyond k, pop the element with the lowest frequency
The heap now contains exactly the k most frequent elements

The sort approach is simpler to code and perfectly fine for interviews. The heap approach is better if you need O(n log k) and k is much smaller than n.

from collections import Counter
import heapq

def topKFrequent(nums, k):
    freq = Counter(nums)
    return [x for x, _ in freq.most_common(k)]

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int n : nums) freq[n]++;
    
    // min-heap of (frequency, number)
    priority_queue<pair<int,int>,
        vector<pair<int,int>>,
        greater<pair<int,int>>> minHeap;
    
    for (auto& [num, cnt] : freq) {
        minHeap.push({cnt, num});
        if (minHeap.size() > k) minHeap.pop();
    }
    
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }
    return result;
}

public int[] TopKFrequent(int[] nums, int k) {
    var freq = new Dictionary<int, int>();
    foreach (int n in nums)
        freq[n] = freq.GetValueOrDefault(n) + 1;
    
    return freq.OrderByDescending(kv => kv.Value)
               .Take(k)
               .Select(kv => kv.Key)
               .ToArray();
}

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums)
        freq.merge(n, 1, Integer::sum);
    
    PriorityQueue<int[]> minHeap =
        new PriorityQueue<>((a, b) -> a[1] - b[1]);
    
    for (var e : freq.entrySet()) {
        minHeap.offer(new int[]{e.getKey(), e.getValue()});
        if (minHeap.size() > k) minHeap.poll();
    }
    
    int[] result = new int[k];
    for (int i = 0; i < k; i++)
        result[i] = minHeap.poll()[0];
    return result;
}

MODULE WEEK 9