DEV Community: Yovo Manolov

Fraudulent activity problem from Hackerrank - sorting problems. Three different solutions. ( min-max heap, counting sort)

Yovo Manolov — Thu, 29 May 2025 21:38:38 +0000

Reference link to the problem:

https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem

*The problem is the following: *

We need to monitor a client's expenditure over a period and issue notifications if the expenditure for a given day is at least twice the median of the expenditure for the preceding 'd' days.

So what is a median:

The median of a finite list of numbers is the "middle" number when those numbers are listed in order from smallest to greatest.

ref: https://en.wikipedia.org/wiki/Median

The solution I tried before looking out for optimization options is the following:

/*
     * Complete the 'activityNotifications' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY expenditure  
     *  2. INTEGER d
     */


    public static int activityNotifications(List<Integer> expenditure, int d) {
        int noticesNumber = 0;

        for (int currentDay = d; currentDay < expenditure.size(); currentDay++) {
            // Extract and sort the sublist of the last 'd' expenditures
            List<Integer> sublistToCheck = expenditure
                    .subList(currentDay - d, currentDay)
                    .stream()
                    .sorted()
                    .collect(Collectors.toList());

            // Calculate the median
            double medianValue;
            if (d % 2 == 1) {
                // Odd number of days: single middle value
                medianValue = sublistToCheck.get(d / 2);
            } else {
                // Even number of days: average of the two middle values
                medianValue = (sublistToCheck.get(d / 2 - 1) 
                                + sublistToCheck.get(d / 2)) / 2.0;
            }

            // Check if the current day's expenditure is at least twice the median
            if (expenditure.get(currentDay) >= medianValue * 2) {
                noticesNumber++;
            }
        }

        return noticesNumber;
    }

*Non-optimized algorithm analysis: *

Initialization ` 'noticesNumber' is initialized to 0

The main loop runs from "currentDay=d" because we need at least 'd' days of data to consider issuing a notification.
`

Extract and sort a sublist:

` For each day 'currentDay' we extract the sublist from 'currentDay - d' to 'currentDay'.

The sublist represents the last 'd' days' expenditures.

We sort this sublist to facilitate median calculation.
`
Median calculation:

`if 'd' is odd, the median is the middle element of the sorted sublist.

if 'd' is even, the median is the average of the two middle elements.

Note that for even 'd', the average should be calculated using floating point division to ensure precision.`

Notification check :

` We compare the current day's expenditure twice the calculated median.

If the current day's expenditure is at least twice the median, we increment 'noticesNumber'.
`

*Time complexity analysis of the non-optimized solution: *

main loop

The main loop runs n-d times if 'expenditure.size()' is equal to 'n'

*sublist extraction and sorting *

For each iteration of the loop, we extract a sublist of size 'd' from 'expenditure'. This operation has a time complexity of O(d).

The sublist is then sorted using stream.sorted(), which has time complexity of O(dlogd).

median calculation

Calculating the median involves accessing one or two elements of the sorted sublist. The operation is O(1).

notification check

The comparison of the current day's expenditure with twice the median value is simple arithmetic operation, which is O(1)

total time complexity

Sublist extraction and sorting: O(d) + O(dlogd) = O(dlogd) for each iteration.

Median calculation and comparison: O(1) for each iteration.

Since the dominant term is O(dlogd) for each iteration,

The total time complexity of the entire loop is:

_(n-d) * O(dlogd) = O((n-d) * dlogd) _

Which simplified is O(n*dlogd)

Analysis of Min-Max Heap optimized solution

public static int activityNotifications(List<Integer> expenditure, int d) {
        if (expenditure == null || expenditure.size() < d) return 0;

        int noticesNumber = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < d; i++) {
            addNumber(expenditure.get(i), maxHeap, minHeap);
        }

        for (int i = d; i < expenditure.size(); i++) {
            double median = getMedian(maxHeap, minHeap);

            if (expenditure.get(i) >= 2 * median) {
                noticesNumber++;
            }

            if (!maxHeap.remove(expenditure.get(i - d))) {
                minHeap.remove(expenditure.get(i - d));
            }

            addNumber(expenditure.get(i), maxHeap, minHeap);
        }

        return noticesNumber;
    }

    private static void addNumber(int num, PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.add(num);
        } else {
            minHeap.add(num);
        }

        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.add(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }

    private static double getMedian(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (maxHeap.size() == minHeap.size()) {
            return ((double) maxHeap.peek() + minHeap.peek()) / 2;
        } else {
            return maxHeap.peek();
        }
    }

The solution above uses two heaps :

a min-heap :

and a max heap

You can brush up your heap knowledge from this article:

https://www.geeksforgeeks.org/difference-between-min-heap-and-max-heap/

In a Min-Heap the minimum key element is present at the root.

- In a Max-Heap the maximum key element is present at the root.

Algorithm breakdown:
- Initialization

'noticesNumber' is initialized at 0;

Two heaps are used:

maxHeap (a max-heap) stores the lower half of the numbers.
minHeap (a min-heap) stores the upper half of the numbers.

Initial Population

 ...
        for (int i = 0; i < d; i++) {
            addNumber(expenditure.get(i), maxHeap, minHeap);
        }
       ...
          private static void addNumber(int num, 
                   PriorityQueue<Integer> maxHeap,
                   PriorityQueue<Integer> minHeap) {

         /*
         peek - Retrieves, but does not remove, the head of this queue, 
                         or returns null if  this queue is empty. 
        */
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.add(num);
        } else {
            minHeap.add(num);
        }

        if (maxHeap.size() > minHeap.size() + 1) {

            /* poll - Retrieves and removes the head of this queue, 
                  or returns null if this queue is empty  */ 

            minHeap.add(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }

For the first 'd' days, add each expenditure to the appropriate heap using 'addNumber' method.

- Processing subsequent days

For each day from 'd' to the end of the expenditure list:

Compute the median using the 'getMedian' method:

Check if the current day's expenditure is at least twice the median. If so increment 'noticesNumber'

Remove the expenditure From 'd' days ago from the appropriate heap.

Add the current day's expenditure to the appropriate heap.

Heap operations:

'addNumber': Adds a number to one of the heaps and balances the heaps if necessary

 private static void addNumber(int num, PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.add(num);
        } else {
            minHeap.add(num);
        }

        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.add(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }

'getMedian': Computes the median based on the sizes and top elements of the heap

 private static double getMedian(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (maxHeap.size() == minHeap.size()) {
            return ((double) maxHeap.peek() + minHeap.peek()) / 2;
        } else {
            return maxHeap.peek();
        }
    }

Time complexity analysis

Heap operation

Insertion('addNumber'): Each insertion operation into a heaps takes O(logd)

The initial population of Heaps

For the first 'd' elements, we perform 'addNumber' which is O(logd) per insertion, therefore it takes *O(dlogd) *

 private static void addNumber(int num, PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.add(num);
        } else {
            minHeap.add(num);
        }

        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.add(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }

** Time complexity of insertion into a heap: **

Inserting an element into a heap takes O(logd) for a heap of size 'd' because the heap needs to maintain its properties (binary tree structure and heap property)

Rebalancing heaps:

When 'maxHeap' and 'minHeap' are unbalanced, the method involves two primary operations:

Removing the root of one heap, which takes O(logd)
Inserting this element into the other heap, which also takes *O(log d) *

Since rebalancing involves one removal and one insertion, the total time for rebalancing is:

O(logd) + O(logd) =2*O(logd) = O(logd)

In conclusion the Total time complexity for each call to 'addNumber' involves:

One insertion into a heap: O(logd)
Potentially one rebalancing operation O(logd)

Since these operations are sequential and not nested,

*the total time complexity for each call to 'addNumber' remains O(logd) *

Processing subsequent days

For each of the remaining n - d days:

Compute the median O(1)
Remove the old expenditure O(logd)
Add the new expenditure: O(logd)
Each day's operation takes O(logd), and we perform these operations for n-d days, resulting in O((n-d) logd)

Overall the total time complexity of the min-max heap solution is

Initial heap population: O(dlogd)

processing remaining days: O((n-d)logd)

=> O(dlogd) + O((n-d)*logd) = O(nlogd)

Which is significantly more efficient than the O(n*dlogd) time complexity of the non-optimized solution.

*Summary of the min-max heap solution: *

The min-max heap solution efficiency maintains the median for each sliding window of size 'd' using 2 heaps. By leveraging the properties of the heaps, it achieves a time complexity of O(nlogd), making it well-suited for large datasets, compared to the non-optimized sorting-based approach.

Counting sort solution
The implementation of the Counting sort optimization is the following:

import java.util.List;

public class Result {

    public static int activityNotifications(List<Integer> expenditure, int d) {
        int noticesNumber = 0;
       // Assuming expenditures are between 0 and 200 
       // as stated nin th task description. 
       int[] count = new int[201]; 

        // Initialize the count array with the first 'd' expenditures
        for (int i = 0; i < d; i++) {
            count[expenditure.get(i)]++;
        }

        for (int i = d; i < expenditure.size(); i++) {
            int medianValue = getMedian(count, d);

            if (expenditure.get(i) >= 2 * medianValue) {
                noticesNumber++;
            }

            // Update the count array for the sliding window
            count[expenditure.get(i)]++;
            count[expenditure.get(i - d)]--;
        }

        return noticesNumber;
    }


       /*
        If d is even, we need to find the two middle values and take their average.
      If d is odd, we find the single middle value.
      We traverse the count array, accumulating counts until we reach the required                positions to determine the median.
         */


    private static int getMedian(int[] count, int d) {
        int sum = 0;

       int median1 = -1;
        int median2 = -1;

        if (d % 2 == 0) { 

            for (int i = 0; i < count.length; i++) {
                sum += count[i];
                if (median1 == -1 && sum >= d / 2) {
                    median1 = i;
                }
                if (sum >= d / 2 + 1) {
                    median2 = i;
                    break;
                }
            }
            return (median1 + median2) / 2;
        } else {  
            for (int i = 0; i < count.length; i++) {
                sum += count[i];
                if (sum > d / 2) {
                    return i;
                }
            }
        }

        return 0;
    }
}

Algorithm explanation:

Initialization:

'noticesNumber' initialized to 0.

A count array of size 201 is used to keep track of the frequency of expenditures which are restricted by the task conditions within a range of 0 to 200.

The initial population of the count array:

for (int i = 0; i < d; i++) { count[expenditure.get(i)]++; }

The first 'd' elements of the 'expenditure' list are used to populate the 'count' array.

Processing subsequent days:

` for (int i = d; i < expenditure.size(); i++) {
int medianValue = getMedian(count, d);

        if (expenditure.get(i) >= 2 * medianValue) {
            noticesNumber++;
        }

        // Update the count array for the sliding window
        count[expenditure.get(i)]++;
        count[expenditure.get(i - d)]--;
    }`

For each day from 'd' to the end of the 'expenditure' list:

Compute the median using the 'getMedian' method
Check if the current day's expenditure is at least twice the median. If so, increment 'noticesNumber'
Update the 'count' array to reflect the new sliding window

*Median calculation *

private static int getMedian(int[] count, int d) {
        int sum = 0;

       int median1 = -1;
        int median2 = -1;

        if (d % 2 == 0) { 

            for (int i = 0; i < count.length; i++) {
                sum += count[i];
                if (median1 == -1 && sum >= d / 2) {
                    median1 = i;
                }
                if (sum >= d / 2 + 1) {
                    median2 = i;
                    break;
                }
            }
            return (median1 + median2) / 2;
        } else {  
            for (int i = 0; i < count.length; i++) {
                sum += count[i];
                if (sum > d / 2) {
                    return i;
                }
            }
        }

        return 0;
    }

The median method traverses the 'count' array to find the median

For even 'd', it finds the two median values and returns their average

For odd 'd' it finds the single middle value.

Time complexity analysis

The initial population of the count array

Involves iterating through the first 'd' elements of the expenditure list: ** O(d)**

Processing subsequent days:

For each of the remaining n-d days:

*Median Calculation ('getMedian' method) * :

Traversing the 'count' array to find the median takes O(R), where R is the range of possible expenditures (201 in our case)

Updating the count array

Updating the count array involves two constant-time operations for each day.

Time complexity for each day: O(R) + O(1) = O(R)

Since we perform these operations for n-d days, the total time complexity of the loop is O((n-d)*R)

Total time complexity - O(n)

Combining the complexities, we get:

Initial population of the count array: O(d)
Processing the remaining days : O((n-d) *R)

Overal, the total time complexity is:

O(d) + O((n-d) R) = O(d) + (n*R) = O(n*R)

and given that R is 201 we can simplify to:

O(n)

Comparison of the min-max heap solution to the counting sort solution

Based on time complexity:

The counting sort approach has a time complexity of O(nd)

while the min-max heap approach has a time complexity of O(nlogd)

Winner: The min-max heap approach is generally more efficient in terms of time complexity, especially when 'd' is large.

For most practical scenarios where efficiency is crucial, and 'd' is relatively large, the min-max heap approach is better. However, for cases with a small fixed range of expenditures, the counting sort approach might be sufficient and simpler to implement.

Sherlock and anagrams (hacker rank) from the Dictionaries and Hashmaps section + extensive time and space complexity analysis.

Yovo Manolov — Thu, 29 May 2025 21:10:30 +0000

Hi, guys, today we will discuss the problem "Sherlock and anagrams"

The link to the problem is the following:

https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Short description of the problem:

Anagram definition:
Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string.

The task is to:

Find the number of pairs of substrings of a given string that are anagrams of each other.

Example 1:

string = mom

The list of all anagrammatic pairs is: [m,m], [mo, om] at positions [[0],[2]], [[0.1], [1,2]] respectivly. The result will be 2, as we have 2 anagrammatic pairs.

We have a function sherlockAndAnagrams that has the following parameter(s):

string s: the given string

The function should return the number of unordered anagrammatic pairs of substrings in s

Example 2:

string: abba

anagrammatic pairs: ( a, a | b, b | ab, ba| abb, bba ) which are 4 in total.

So, the important thing for me is the thought process when I solve those tasks.

What I was initially thinking when I read the problem description was the following:

Those are dictionary problems, so we need to use dictionary data structures.
We need to convert the string to a char array to manipulate it easier.
We need to store the substrings with equal length in separate hashmaps

... but in order to make the processing easy we may use embedded hashmap. The outer hashmap will store the length of the substrings in the inner hashmap, and the inner hashmap will store the strings themselves as a key and the occurrence count as a value.

The hardest thing for me to figure out was that, to count the pairs, they need to be equal as a value. Otherwise, I couldn't do it, so, before adding the strings to the HashMap with correspondent length, we need to use sorting on the substring, to make the anagram pairs look alike. If we represent the substrings as a char array, the sorting could be easily done in Java using the method java.util.Arrays.sort(string).
And the last thing is that if we keep the count of equal substrings with the same length we need a way to calculate the pairs. This can be achieved using this formula :

** pairsCount = (numberOfEqualSubstrings * (numberOfEqualSubstrings - 1) )/2

**
or pc = (n*(n-1))/2

let's see how this works:

if we have the substrings - "a" "a" "a" "a" in the inner HashMap

with values HashMap<"a", 6> for example then we shoud have 6 anagram pairs

*(4*3)/2 = 6 *

the 6 anagrammatic pairs are

//letter(index)

a(0) a(1)

a(1) a(2)

a(2) a(3)

a(0) a(2)

a(1) a(3)

a(0) a(3)

Which are 6 pairs

So an example solution to the problem is the following:

public static int sherlockAndAnagrams(String s) {

    // HashMap<AnagramLength, HashMap<SortedSubstring, Counter>>
    HashMap<Integer, HashMap<String, Integer>> hmAnagrams = new HashMap<>();


    //mininum length of substring is 1 and max is length-1     
    for (int substrLength = 1; substrLength < s.length(); substrLength++) {

        //inner HashMap<equalSubstrings, equalSubstringsCounter>
        HashMap<String, Integer> stringCounterHashMap = new HashMap<>();

        // from index 0 to index (stringLength - substringLength) 
        //so we don't get IndexOutOfBounds exception.
        for (int start = 0; start <= s.length() - substrLength; start++) {

            String substrValue = s.substring(start, start + substrLength);

            String sortedSubstrValue = sortString(substrValue);

            stringCounterHashMap.put(sortedSubstrValue, 
                                    stringCounterHashMap.
                                        getOrDefault(sortedSubstrValue, 0) + 1);
        }

        hmAnagrams.put(substrLength, stringCounterHashMap);
    }

    // Calculate the number of anagrammatic pairs
    int count = 0;
    for (HashMap<String, Integer> map : hmAnagrams.values()) {
        for (int value : map.values()) {
            // if value is 1  we don't have a pair.
            if (value > 1) { 
                // If there are n occurrences of a substring,
                // we can form n * (n - 1) / 2 pairs
                count += (value * (value - 1)) / 2;
            }
        }
    }

    return count;
}

// Helper function to sort characters of a string
private static String sortString(String inputString) {
    char[] tempArray = inputString.toCharArray();
    java.util.Arrays.sort(tempArray);
    return new String(tempArray);
}

Time and Space complexity analysis

For this article, I'll dive a little deeper into time and space complexity analysis, so if you don't enjoy this part as much you're free to skip it.

Time complexity:

Outer loop over Substring lengths:

for (int substrLength = 1; substrLength < s.length(); substrLength++) { ... }

This loop runs in n - 1 times where n is the length of the input string.

Inner loop over given string indexes:

for (int start = 0; start <= s.length() - substrLength; start++) { ... }

For each substring length "substrLength", the inner loop runs n - substrLength +1 times.

Substring and sorting:
String substrValue = s.substring(start, start + substrLength); String sortedSubstrValue = sortString(substrValue);
Simple logarithm examples:

To refresh your log knowledge refer to the link in the image description above.

for reference here is the algorithms time complexity chart:

HashMap put and getOrDefault operations take O(1) constant runtime complexity on average.

Combining all these steps, the time complexity for processing each substring can be approximated by:

if we represent "substrLength" as n , then

O(n + nlogn) = O(nlogn)

So why is this expression true?

The expression O(n+nlogn) simplifies to O(n log n) due to the properties of the Big-O notation. 

Big O notation describes the upper bound of an algorithm's complexity, focusing on the dominant term(s) as input size n grows. Here is why O(n + nlogn) = (Onlogn): 

1. Dominant Term: In the expression O(n+ nlogn)  

* n grows learly 
*  nlogn grows faster than n for sufficiently large n because log n 
(though it grows slower than any polynomial ) 
is still an icreasing function. 

(definition of polynomial function: A polynomial function is a function such as a quadratic, a cubic, a quartic, and so on, involving only non-negative integer powers of x)

2. Asymptotic Behaviour: 

As n becomes very large, the nlogn term will dominate the n term. 
This is because the logarithmic factor makes nlogn grow faster than n alone. 

For example: 

When n = 10, log n ≈ 3.3, so nlog ≈ 33
When n = 100, log n  ≈ 6.6 so nlogn ≈ 66
When n = 1000, log n ≈ 1000 so nlogn ≈ 9900 

In each case nlogn grows significantly faster than n. 

3. Big O simplification 

In Big-O notation, we only consider the term with the highest growth rate because it dominates the overall complexity as n increases. Lower-order terms and constant factors are omitted. Therefor,  O(n+nlogn) simplifies to O(nlogn) because : 

n+nlogn <= c * nlogn for same constant c and sufficiently large n.

In conclusion, O(n+nlogn) = O(n logn) because the nlogn term dominates the liner n term as n grows larger.

If we only discuss the inner for loop that processes substrings of equal length then we can look at this logic:

for (int start = 0; start <= s.length() - substrLength; start++) {
       String substrValue = s.substring(start, start + substrLength);

            String sortedSubstrValue = sortString(substrValue);

            stringCounterHashMap.put(sortedSubstrValue, 
                                    stringCounterHashMap.
                                        getOrDefault(sortedSubstrValue, 0) + 1);
}

If the inner for loop time complexity is О(n^2logn) and the Outer loop has approximate

time complexity of O(n), so we can say that the total time complexity is :

Space Complexity:

*HashMaps: *

hmAnagrams stores a HashMap for each substring length with all unique sorted substrings as keys.
The number of unique substrings of any length is at most n(n+1)/2

Example :

*Substrings and Sorted substrings: *

Each sorted substring is stored in the inner HashMap, leading to O(n^2) space for substrings
The space complexity for all substrings combined is O(n^3) in the worst case because we store O(n^2) substrings, each of length up to n

Auxiliary Space:

Temp variables, counters, and all other small variables contribute negligible space compared to the HashMaps.

I hope you enjoyed this one as well.

Array Manipulation Hackerrank problem analysis and solution optimization (prefix sum + difference array)

Yovo Manolov — Thu, 29 May 2025 20:50:34 +0000

Hi, guys, today I want to analyze the Array Manipulation problem from Hackerrank. We will take a look at a suboptimal solution, which is naturally easiest to figure out. Then we will discuss, analyze, and understand an optimized version that solves this problem which uses prefix sum and a difference array to achieve the needed time complexity.

For starters, this is the link to the problem: https://www.hackerrank.com/challenges/crush/problem?h_l=interview%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

Short problem description:

So, we have "n" which is the length of the array that we will populate, taking the data from the double LinkedList queries parameter.

For example, the linked list contains the following data:

queries = [[1,5,3],[4,8,7],[6,9,1]]

each sublist has 3 integers e.g. [1,5,3]

(1) is the one-based index, from which we need to start populating the n-length array.
(5) is also a one-based index where we need to stop populating the array.
(3) that's the value that we will use to populate the array.

When I say populate In the task the population is an addition operation.

The expected return value of the method after all iterations is to return the max element value from the array with length n

In the example above that's the value 10.

Suboptimal solution:

So my solution was not optimal but it demonstrates the basic logic that needs to be applied to solve the problem:

public static long arrayManipulation(int n, List<List<Integer>> queries) {

        long maxVal = Integer.MIN_VALUE;

        int[] calcArray = new int[n];  // the array in which the data will be calculated

        for(List<Integer> q : queries){  //queries length  can be up to 2*10^5 
            int fromIndex = q.get(0);        
            int toIndex = q.get(1);
            int valueToApply= q.get(2);

             // here I use the same array to do the addition operation as well as 
            // finding the max value in the array.
            for(int j=fromIndex-1 ;j < toIndex  ;j++){
                calcArray[j] += valueToApply;    
                if(maxVal < calcArray[j]) maxVal = calcArray[j];
            }        
        }

        return maxVal;
    }

Worst case time complexity of this solution is O(m*n)

where:

m - number of queries

n - is the scope (fromIndex-1 - toIndex-1)

*Space complexity: *

The array:

calcArray is of size n, so it requires O(n) space.

The Queries:

queries list contains 'm' sublists each of 3 integers. The list requires O(m) space. So the overall space complexity is O(n+m)

So the overall space complexity is O(n+m)

The optimised approach

The optimized approach requires a technique named "Prefix sum"

So what is prefix sum:

`Input: arr[] = {10, 20, 10, 5, 15}
Output: prefixSum[] = {10, 30, 40, 45, 60}

Explanation: While traversing the array, update the element by adding it with its previous element.

prefixSum[0] = 10,
prefixSum[1] = prefixSum[0] + arr[1] = 30,
prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on.`

How do we combine the prefix sum approach with diffArray to achieve time complexity of O(n+m) for the final updated array, instead of O(n*m) for the previous example

The purpose of the "difference array" in the prefix sum approach is to efficiently handle range updates on an array, instead of directly updating each element in the specified range of each query. The differenceArray allows us to make constant-time updates, which can be processed to get the final array values.

Let's take a look at a step-by-step explanation of how the difference array works:

Initialization:

First, we create a difference array of size n+1 to handle the range updates at the boundaries.

Applying updates:

For a query that adds a value v from index a to b:

Increment diffArray[a-1] by v
(starting the increment at the index a).

Decrement diffArray[b] by v
(ending the increment after the index b).

Calculating final values:

We use the prefix sum approach described above applied to the difference array to calculate the final array.

The prefix sum of the diffArray at any point gives us the net effect of all updates up to that index.

Let's see a simple example of the diff array and prefix sum methods combined:

If we have the following conditions:
`n = 5 // size of the array

queries = [
[1, 2, 100],
[2, 5, 100],
[3, 4, 100]
]`

we initialize the diffArray which must have a size of n+1 = 6

diffArray = [0, 0, 0, 0, 0, 0]

We apply the first query [1,2,100]

`//Increment diffArray[a -1] by v (index 0 by 100)
// Decrement diffArray[b] by v (decr index 2 by 100)

diffArray = [100, 0, -100, 0, 0, 0]`

We apply the second query [2,5,100]

`//Increment diffArray[a-1] by v ( index 1 by 100 )
// Decrement diffArray[b] by v (decr index 5 by 100 )

diffArray = [100, 100, -100, 0, 0, -100]`

We apply the third query [3,4, 100]

`//Increment diffArray[a-1] by v ( index 2 by 100 ) from -100 to 0
// Decrement diffArray[b] by v (decr index 4 by 100 ) from 0 to -100

diffArray = [100, 100, 0, 0, -100, -100]`

Calculate the final values using the prefix sum: `currentSum = 0 finalArray[0] = currentSum += diffArray[0] ; finalArray[1] = currentSum += diffArray[1] ; finalArray[2] = currentSum += diffArray[2] ; finalArray[3] = currentSum += diffArray[3] ; finalArray[4] = currentSum += diffArray[4] ;

result:
finalArray = [100, 200, 200, 200, 100] `

Using the difference array, each query update is done in O(1) time complexity, and calculating the final values from the difference array takes O(n) time, making the overall time complexity O(n+m), which makes this approach significantly more time efficient than directly updating the array for each query. The space complexity is O(n) for the diff array and O(m) for the queries.

Thus, the optimized space complexity remains O(n+m)

This is an example of the prefix sum + difference array problem solution :

public static long arrayManipulation(int n, List<List<Integer>> queries) {
    long[] diffArray = new long[n + 1];  // Using a diff array for range updates

    // Process each query and update the diffArray
    for (List<Integer> q : queries) {
        int fromIndex = q.get(0) - 1;
        int toIndex = q.get(1);
        int valueToApply = q.get(2);

        diffArray[fromIndex] += valueToApply;
        if (toIndex < n) {
            diffArray[toIndex] -= valueToApply;
        }
    }

    // Find the maximum value using the prefix sum array
    long maxVal = Long.MIN_VALUE;
    long currentSum = 0;
    for (int i = 0; i < n; i++) {
        currentSum += diffArray[i];
        if (currentSum > maxVal) {
            maxVal = currentSum;
        }
    }

    return maxVal;
}

Implementation tips for Java:

the parallel prefix implementation could be replaced by the
prefixedSumArray = Arrays.parallelPrefix(diffArray, Math::addExact);

also extracting the max value could be replaced by
Collections.max(Arrays.asList(arr));

If you reached the end, I'm glad the article was interesting for you : )

New Year Chaos - HackerRank algorithmic problem - clarifying comments

Yovo Manolov — Tue, 20 May 2025 22:47:40 +0000

   The name of the problem is New Year Chaos.

Here is a link to the problem in HackerRank:

https://www.hackerrank.com/challenges/new-year-chaos

Problem description :

Initially, I tried to solve it independently but failed miserably.

Then I found this video with a good explanation:

Credits to: @aditya Pandey for the solution that I used.

https://www.youtube.com/watch?v=RGv_K72p86M

However, I still missed some ideas that the solver (Aditya) had in his mind, so I added some additional comments to his solution when I fully understood the way it works :

 /*
     * Complete the 'minimumBribes' function below.
     *
     * The function accepts INTEGER_ARRAY q as parameter.
     */

    /* If we take an input array of numbers:
              Integer[] arr = {2, 1, 5, 3, 4};
            minimumBribes(Arrays.asList(arr));

    Then the comments in this method apply to the above input array.
    */
    private static void minimumBribes(List<Integer> q) {

        int bribesCounter = 0;
        boolean flag = false;

        for(int i = q.size(); i>=1; i--){

            if(q.get(i-1) != i) { //is the last element different than i (5)

                if((i-2)>=0 && q.get(i-2)==i){
                    //we have single bribe occurring

                    /*this will handle the first two elements
                    at the second iteration of the base for loop.*/

                    //swap the values when we have single bribe
                    int swap1 = q.get(i-1); //latest unordered element that is not in the correct position
                    int swap2 = q.get(i-2); //the element next to the latest element also not in the correct position.
                    q.set(i-1, swap2);
                    q.set(i-2, swap1);

                    bribesCounter++;
                } else if ((i-3) >= 0 && q.get(i-3) == i){
                    /*first iteration of the base for loop will first
                     fix the last three numbers in the array: which are 5 ,3 and 2
                    */

                    //double bribe

                    //i-3 is equal to i and i-2 is not
                    //e.g. 2 1 | 5 (i-3)  3 (i-2) 4 (i-1)

                    //swap operations
                    int swap1 = q.get(i-1); //4
                    int swap2 = q.get(i-2); //3
                    int swap3 = q.get(i-3); //5

                    q.set(i-1, swap3); // 5
                    q.set(i-2, swap1); // 4
                    q.set(i-3, swap2); // 3

                    bribesCounter+=2;

                } else {
                    //more than 2 consecutive bribes
                    flag = true;
                    break;
                }
            }
        }

        System.out.println(flag ? "Too chaotic" : bribesCounter);

    }

    public static void main(String[] args) throws IOException {
        Integer[] arr = {2, 1, 5, 3, 4};
        minimumBribes(Arrays.asList(arr));

        Integer[] arr2 = {2, 5, 1, 3, 4};
        minimumBribes(Arrays.asList(arr2));
    }

    /*output :
     ==========  
     3
     Too chaotic
     ===========
     */