Solution Explanation:

This problem can be efficiently solved using a greedy approach. The goal is to maximize the number of apples we can put in the basket, given a weight limit of 5000. The key insight is that to maximize the number of apples, we should prioritize adding the lightest apples first. Heavier apples will consume more of the weight limit, potentially preventing us from adding more apples overall.

Algorithm:

1. Sort: Sort the weight array in ascending order. This ensures that we consider the lightest apples first.
2. Iterate and Accumulate: Iterate through the sorted weight array. In each iteration:
   • Add the current apple's weight to a running sum s.
   • If s exceeds 5000, it means we've exceeded the weight limit. Return the current index i (the number of apples added so far).
3. All Apples Fit: If the loop completes without exceeding the weight limit, it means all apples can fit in the basket. Return the total number of apples (weight.length).

Time Complexity: O(n log n), dominated by the sorting step. The iteration through the sorted array takes O(n) time.

Space Complexity: O(log n) or O(n) depending on the sorting implementation. Many sorting algorithms (like merge sort) have O(log n) space complexity, while others (like quicksort) can have O(n) in the worst case. In-place sorting algorithms can achieve O(1) space complexity.

Code Implementation in Different Languages:

The following code snippets demonstrate the solution in various programming languages. They all follow the same algorithmic steps outlined above.

Python3:

class Solution:
    def maxNumberOfApples(self, weight: List[int]) -> int:
        weight.sort()
        s = 0
        for i, x in enumerate(weight):
            s += x
            if s > 5000:
                return i
        return len(weight)

Java:

import java.util.Arrays;
 
class Solution {
    public int maxNumberOfApples(int[] weight) {
        Arrays.sort(weight);
        int s = 0;
        for (int i = 0; i < weight.length; ++i) {
            s += weight[i];
            if (s > 5000) {
                return i;
            }
        }
        return weight.length;
    }
}

C++:

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int maxNumberOfApples(std::vector<int>& weight) {
        std::sort(weight.begin(), weight.end());
        int s = 0;
        for (int i = 0; i < weight.size(); ++i) {
            s += weight[i];
            if (s > 5000) {
                return i;
            }
        }
        return weight.size();
    }
};

Go:

import "sort"
 
func maxNumberOfApples(weight []int) int {
	sort.Ints(weight)
	s := 0
	for i, x := range weight {
		s += x
		if s > 5000 {
			return i
		}
	}
	return len(weight)
}

TypeScript:

function maxNumberOfApples(weight: number[]): number {
    weight.sort((a, b) => a - b);
    let s = 0;
    for (let i = 0; i < weight.length; ++i) {
        s += weight[i];
        if (s > 5000) {
            return i;
        }
    }
    return weight.length;
}

These code examples all implement the same efficient greedy algorithm, demonstrating its adaptability across multiple programming languages. The choice of language primarily impacts the syntax and specific sorting function used, but the core logic remains consistent.