Solution Explanation for Maximum Score From Removing Stones

This problem involves finding the maximum score achievable in a game where you remove stones from three piles. The key insight is that the game ends when fewer than two piles have stones remaining. This means the maximum score is limited by the smaller two piles.

Approach 1: Iterative Greedy Approach

This approach simulates the game directly. We sort the piles and iteratively remove one stone from the two largest piles until one of the two largest piles becomes empty. The number of iterations represents the maximum score.

Time Complexity: O(n log n), where n is the maximum number of stones in any pile. This is due to the sorting operation which has a time complexity of O(n log n) in the worst case, and the while loop iterates at most n times.

Space Complexity: O(1) because we use constant extra space regardless of the input size.

Approach 2: Optimized Mathematical Approach

This approach uses a mathematical observation to efficiently determine the maximum score without explicitly simulating the game. Let's say we have piles of size a, b, and c.

1. Sort: Sort the piles in ascending order (a ≤ b ≤ c).
2. Check for Limiting Case: If a + b < c, then the maximum score is a + b. This is because, once a and b are empty, the game ends, regardless of the remaining stones in c.
3. Calculate Score: Otherwise, the maximum score is (a + b + c) // 2. This is because you can always take stones from the two largest piles until either one of them becomes equal to the smallest pile or one becomes empty. The total number of moves will be determined by the total number of stones divided by 2 (since we remove two stones each turn), rounded down.

Time Complexity: O(log n), dominated by the sorting operation using a efficient algorithm like merge sort.

Space Complexity: O(1).

Code Examples in Different Languages

The code examples below illustrate both approaches. Approach 2 is generally preferred due to its improved time complexity.

Approach 1 (Iterative Greedy):

Python:

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        s = sorted([a, b, c])
        ans = 0
        while s[1]:
            ans += 1
            s[1] -= 1
            s[2] -= 1
            s.sort()
        return ans
 

Java:

import java.util.Arrays;
 
class Solution {
    public int maximumScore(int a, int b, int c) {
        int[] s = new int[] {a, b, c};
        Arrays.sort(s);
        int ans = 0;
        while (s[1] > 0) {
            ++ans;
            s[1]--;
            s[2]--;
            Arrays.sort(s);
        }
        return ans;
    }
}

C++:

#include <vector>
#include <algorithm>
 
class Solution {
public:
    int maximumScore(int a, int b, int c) {
        std::vector<int> s = {a, b, c};
        std::sort(s.begin(), s.end());
        int ans = 0;
        while (s[1]) {
            ++ans;
            s[1]--;
            s[2]--;
            std::sort(s.begin(), s.end());
        }
        return ans;
    }
};

Go:

import "sort"
 
func maximumScore(a int, b int, c int) int {
	s := []int{a, b, c}
	sort.Ints(s)
	ans := 0
	for s[1] > 0 {
		ans++
		s[1]--
		s[2]--
		sort.Ints(s)
	}
	return ans
}

Approach 2 (Optimized Mathematical):

Python:

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        a, b, c = sorted([a, b, c])
        if a + b < c:
            return a + b
        return (a + b + c) // 2

Java:

import java.util.Arrays;
 
class Solution {
    public int maximumScore(int a, int b, int c) {
        int[] s = new int[] {a, b, c};
        Arrays.sort(s);
        if (s[0] + s[1] < s[2]) {
            return s[0] + s[1];
        }
        return (a + b + c) / 2;
    }
}

C++:

#include <vector>
#include <algorithm>
 
class Solution {
public:
    int maximumScore(int a, int b, int c) {
        std::vector<int> s = {a, b, c};
        std::sort(s.begin(), s.end());
        if (s[0] + s[1] < s[2]) return s[0] + s[1];
        return (a + b + c) / 2;
    }
};

Go:

import "sort"
 
func maximumScore(a int, b int, c int) int {
	s := []int{a, b, c}
	sort.Ints(s)
	if s[0]+s[1] < s[2] {
		return s[0] + s[1]
	}
	return (a + b + c) / 2
}

These examples demonstrate both approaches, allowing for a comparison of their implementations and efficiency. The mathematical approach (Approach 2) is generally preferred for its better time complexity.