Solving Minimum Steps Problem with O(n log n) Complexity: A Dart Approach

Given an array of N integers, you have to find how many times you have to add up the smallest numbers in the array until their Sum becomes greater or equal to K.

Problem Statement

• List size is at least 3.
• All numbers will be positive.
• Numbers could occur more than once , (Duplications may exist).
• Threshold K will always be reachable.

minimumSteps({1, 10, 12, 9, 2, 3}, 6)  ==>  return (2)

Explanation:

• We add two smallest elements (1 + 2), their sum is 3 .
• Then we add the next smallest number to it (3 + 3) , so the sum becomes 6 .
• Now the result is greater or equal to 6 , Hence the output is (2) i.e (2) operations are required to do this .

minimumSteps({8 , 9, 4, 2}, 23)  ==> return (3)

Explanation

• We add two smallest elements (4 + 2), their sum is 6 .
• Then we add the next smallest number to it (6 + 8) , so the sum becomes 14 .
• Now we add the next smallest number (14 + 9) , so the sum becomes 23 .
• Now the result is greater or equal to 23 , Hence the output is (3) i.e (3) operations are required to do this .

minimumSteps({19,98,69,28,75,45,17,98,67}, 464)  ==>  return (8)

Explanation

• We add two smallest elements (19 + 17), their sum is 36 .
• Then we add the next smallest number to it (36 + 28) , so the sum becomes 64 .
• We need to keep doing this until the sum becomes greater or equal to K (464 in this case), which will require 8 Steps .

Expected Time Complexity O(n Log n)

Sample

import "package:test/test.dart";
import "package:solution/solution.dart";

void main() {
  group("Fixed tests", () {
    test("minimumSteps([4, 6, 3], 7)", () {
      expect(minimumSteps([4, 6, 3], 7), equals(1));
    });
    test("minimumSteps([1, 10, 12, 9, 2, 3], 6)", () {
      expect(minimumSteps([1, 10, 12, 9, 2, 3], 6), equals(2));
    });
    test("minimumSteps([10, 9, 9, 8], 17)", () {
      expect(minimumSteps([10, 9, 9, 8], 17), equals(1));
    });
    test("minimumSteps([8, 9, 10, 4, 2], 23)", () {
      expect(minimumSteps([8, 9, 10, 4, 2], 23), equals(3));
    });
    test("minimumSteps([19, 98, 69, 28, 75, 45, 17, 98, 67], 464)", () {
      expect(minimumSteps([19, 98, 69, 28, 75, 45, 17, 98, 67], 464), equals(8));
    });
    test("minimumSteps([4, 6, 3], 2)", () {
      expect(minimumSteps([4, 6, 3], 2), equals(0));
    });
  });
}

My Approach

int minimumSteps(List<int> nums, int value) {
  // sorting the array to get a time complexity of O(n log n):
  nums.sort();
  int sum = 0;
  int steps = 0;
  
  for (int num in nums){
    if (sum >= value) break;
    sum += num;
    steps++;
  }
  return steps-1;
}

In order to achieve a time complexity of (n log n), the array is sorted using the .sort() method. This step is crucial as it allows us obtain a O(n log n) time as stated in the problem statement.

Please note that it is possible to loop over an unsorted array to find the minimum value in O(n) time. In a sorted array, accessing the smallest value takes O(1) time, allowing for quick computations.

After sorting, a for loop iterates over the array to sum up the integers. The steps variable keeps track of the number of times we go through the array to obtain a sum greater or equal to the provided value.

The steps-1 is returned because the counting is 0-indexed. This means that the actual number of steps taken is one less than the steps variable after the loop completes. This adjustment ensures that the returned value accurately reflects the number of operations needed to reach or exceed the value.

By following this approach, the solution maintains the desired time complexity of O(n log n).

Wrapping Up

There you go! Let me know what better approach you have to solving the above problems. ;)

Problem statement source: Codewars

references to achieve solution: https://stackoverflow.com/questions/44200606/faster-way-to-find-min-and-max-values-in-array

About Me

I am Zaahra, a Google Women Techmakers Ambassador who enjoy mentoring people and writing about technical contents that might help people in their developer journey. I also enjoy building stuffs to solve real life problems.

To reach me:

LinkedIn: https://www.linkedin.com/in/faatimah-iz-zaahra-m-0670881a1/

X (previously Twitter): _fz3hra

GitHub: https://github.com/fz3hra

Cheers,

Umme Faatimah-Iz-Zaahra Mujore | Google Women TechMakers Ambassador | Software Engineer