Richest Customer Wealth

Q: Quelle est la complexité temporelle de « Richest Customer Wealth » ?

O(m × n) pour m clients et n banques, car chaque solde est additionné une fois. Aucun algorithme ne peut ignorer une cellule, car tout solde ignoré pourrait être celui qui ferait de son propriétaire la personne la plus riche. Le maximum courant utilise un espace supplémentaire de O(1) .

Q: Les sommes peuvent-elles dépasser la capacité d’un entier de 32 bits ?

Pas ici. Une ligne contient au plus 100 soldes d’au plus 10^4 , donc le total est d’au plus 10^6 , bien inférieur à 2^31 - 1 . Avec des limites plus élevées, tu additionnerais dans un entier de 64 bits.

DébutantTableaux et chaînes

+10

Une banque conserve une grille accounts avec m lignes, une par client, et n colonnes, une par banque : accounts[i][j] correspond à l’argent que le client i possède dans la banque j. La richesse d’un client est le total de sa ligne. Renvoyez la richesse du client le plus riche.

Fonction

maximumWealth(accounts: integer-2d-array) → integer

accountsinteger-2d-array: la grille des soldes, une ligne par client et une colonne par banque
Renvoieinteger: le total de ligne le plus élevé

Contraintes

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100, et chaque ligne a la même longueur.
0 ≤ accounts[i][j] ≤ 10⁴

Exemples

Entrée: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Sortie: 14
Explication: Les lignes totalisent 2 + 8 + 1 = 11, 5 + 5 + 4 = 14 et 7 + 0 + 3 = 10. Le client du milieu en a le plus, 14, même si le solde individuel le plus élevé, 8, appartient à quelqu’un d’autre.

Entrée: accounts = [[3], [9], [4]]
Sortie: 9
Explication: Chaque client utilise une banque, donc les totaux sont 3, 9 et 4, et la réponse est 9.

+14 tests cachés à la soumission

Solution

Chaque solde appartient à un seul client, vous devez donc lire toute la grille : aucune approche ne fait mieux qu’un temps de O(m × n). Le choix porte sur la quantité que vous conservez pendant la lecture. Une liste de tous les totaux fonctionne, mais seul le total le plus élevé observé jusqu’ici compte, donc un seul nombre suffit.

Liste tous les totaux, puis choisis le plus grand

Intuition

Divise la tâche en deux. Parcours d’abord chaque ligne et additionne ses soldes, en stockant un total par client. Pour le premier exemple, cela donne [11, 14, 10]. Parcours ensuite cette liste pour trouver sa valeur la plus élevée, 14.

Le travail est correct : chacun des m × n soldes est additionné une fois, et le deuxième passage lit m totaux. Pour une grille de 100 × 100, cela représente 10^4 additions. Le coût, c’est la liste elle-même : m nombres supplémentaires que tu conserves uniquement pour jeter tous les autres sauf un.

Algorithme

Crée une liste vide totals.
Pour chaque ligne, additionne ses soldes et ajoute la somme à totals.
Initialise richest avec le premier total.
Remplace richest par tout total supérieur, puis retourne-le.

def maximumWealth(accounts):
    # First pass: every customer's total wealth.
    totals = []
    for customer in accounts:
        wealth = 0
        for money in customer:
            wealth += money
        totals.append(wealth)
    # Second pass: the largest total.
    richest = totals[0]
    for wealth in totals:
        if wealth > richest:
            richest = wealth
    return richest

Conserver un maximum courant

Intuition

Une fois le total d’une ligne connu, la seule question est de savoir s’il dépasse le meilleur total obtenu jusqu’ici. Comparez-le donc immédiatement et conservez un seul nombre, richest. Dans le premier exemple, richest passe par 0 → 11 → 14 et reste à 14 lorsque la dernière ligne donne un total de 10.

Initialisez richest à 0. C’est sûr, car aucun solde n’est négatif : chaque total est donc au moins égal à 0, et une grille remplie de zéros renvoie correctement 0. Si les soldes pouvaient être négatifs, vous commenceriez par le total de la première ligne.

Le total maximal possible est de 100 × 10^4 = 10^6, donc un entier de 32 bits peut contenir chaque somme.

Algorithme

Définis richest à 0.
Pour chaque ligne, additionne ses soldes dans wealth.
Si wealth > richest, définis richest à wealth.
Après la dernière ligne, renvoie richest.

def maximumWealth(accounts):
    richest = 0  # money is never negative, so 0 is a safe start
    for customer in accounts:
        richest = max(richest, sum(customer))
    return richest

Pièges et cas limites

Les boucles sont courtes. Les bogues viennent d’une confusion sur le sens dans lequel on parcourt les clients.

Faire la somme des colonnes au lieu des lignes. Une colonne représente une banque pour tous les clients ; son total répond à une autre question. Dans le premier exemple, les colonnes totalisent 14, 13 et 8, et la première ne correspond à la bonne réponse que par chance.
Renvoyer le solde individuel le plus élevé. 8 est le plus grand nombre de la première grille, mais son propriétaire possède 11 au total, soit moins que les 14 du client dont le solde ne dépasse pas 5.
Réinitialiser le total de la ligne au mauvais endroit. Définissez wealth à 0 dans la boucle sur les lignes, avant la boucle interne. Définissez-le une seule fois à l’extérieur, et chaque client hérite de l’argent du client précédent.

Questions fréquentes3

Quelle est la complexité temporelle de « Richest Customer Wealth » ?

O(m × n) pour m clients et n banques, car chaque solde est additionné une fois. Aucun algorithme ne peut ignorer une cellule, car tout solde ignoré pourrait être celui qui ferait de son propriétaire la personne la plus riche. Le maximum courant utilise un espace supplémentaire de O(1).

Comment trouver la somme maximale des lignes d’un tableau à deux dimensions ?

Parcourez les lignes, additionnez chacune d’elles et conservez la somme la plus élevée dans une variable. De nombreux langages raccourcissent la boucle interne à l’aide d’une fonction intégrée de somme, comme max(sum(row) for row in accounts) en Python. Dans les deux cas, vous lisez chaque cellule une seule fois.

Les sommes peuvent-elles dépasser la capacité d’un entier de 32 bits ?

Pas ici. Une ligne contient au plus 100 soldes d’au plus 10^4, donc le total est d’au plus 10^6, bien inférieur à 2^31 - 1. Avec des limites plus élevées, tu additionnerais dans un entier de 64 bits.

Python

def maximumWealth(accounts):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]

Attendu