Code used in "Write efficient code using Data Structures in Salesforce Apex | Reduce Time Complexity using Map" video on SFDC Stop (https://youtu.be/KJOt-QVNOds)

solvingrealworldproblemusingmapapex.cls

// * Link accounts with parent accounts

Update 10,000 accounts
-----------------------

// * Brute Force Approach - Very time consuming

List<Account> accounts = [SELECT Reference_ID__c, Parent_Reference_ID__c FROM Account];
List<Account> accountsToUpdate = new List<Account>();

for(Account childAccount : accounts) { // * 10,000 times
    for(Account parentAccount : accounts) { // * 10,000 times
        // * These statements will execute 10,000 * 10,000 times 10^6 times
        if(childAccount.Parent_Reference_ID__c == parentAccount.Reference_ID__c) {
            childAccount.ParentId = parentAccount.Id;
            accountsToUpdate.add(childAccount);
        }
    }
}

update accountsToUpdate;

Time Complexity
------------------

1 -> n checks
n -> n*n checks

O(n^2) - BAD

// * Optimized Approach

Update 10,000 accounts
-----------------------

List<Account> accounts = [SELECT Reference_ID__c, Parent_Reference_ID__c FROM Account];
List<Account> accountsToUpdate = new List<Account>();

Map<Decimal, Id> accountIdMap = new Map<Decimal, Id>();

for(Account account : accounts) {
    accountIdMap.put(account.Reference_ID__c, account.Id);
} // * Execute 10,000 times - n times

for(Account account : accounts) {
    if(accountIdMap.containsKey(account.Parent_Reference_ID__c)) {
        account.ParentId = accountIdMap.get(account.Parent_Reference_ID__c); // O(1)
        accountsToUpdate.add(account);
    } // * 10,000 times
} // * Execute 10,000 times - n times

update accountsToUpdate;

n+n = 2*n

O(2*n) => O(n) - GOOD