What is the time complexity of Number of Atoms?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Number of Atoms?

This problem uses Hash Table, String, Stack, Sorting. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Number of Atoms?

Insight 1: The use of a stack is crucial for handling the nested parentheses and correctly applying multipliers to the atom counts within each group. Insight 2: A hash map (or dictionary) is essential to efficiently store and update the counts of each atom as the formula is parsed.

Which companies ask LeetCode 726. Number of Atoms in interviews?

This problem is frequently asked at Confluent, Coupang, Docusign, Fastenal.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Number of Atoms - LeetCode 726 Solution

Number of Atoms - Complete Solution Guide

Number of Atoms is LeetCode problem 726, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a string formula representing a chemical formula, return the count of each atom . The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name. One or more digits representing that element's count may follow if the count is greater than 1 . If the count is 1 , no digits will follow. For example, "H2O" and "H2O2" are possible, but "H1O2" is impossible. Two formulas are concatenated together to produce another formula. For example,

Detailed Explanation

The problem asks us to take a chemical formula string as input and return a string representing the count of each atom in the formula, sorted alphabetically. The formula can contain atomic elements (starting with an uppercase letter), numbers representing counts, parentheses for grouping, and concatenation of formulas. The output should be formatted as the element name followed by its count if the count is greater than 1, all concatenated together. For example, 'H2O' should return 'H2O', and 'Mg(OH)2' should return 'H2MgO2'. The input string is guaranteed to be a valid formula and the counts fit within a 32-bit integer.

Solution Approach

The provided code uses a stack-based approach to parse the chemical formula. It iterates through the string, maintaining a stack of hash maps (or dictionaries). Each hash map on the stack represents the atom counts at a particular level of nesting within parentheses. When an opening parenthesis is encountered, a new hash map is pushed onto the stack. When a closing parenthesis is encountered, the hash map on the top of the stack is popped, and its counts are multiplied by the number following the parenthesis (if any) and added to the counts in the hash map below it. Atomic elements and their counts are parsed and added to the hash map at the top of the stack. Finally, the atom counts in the bottom hash map are sorted alphabetically, and the result string is constructed.

Step-by-Step Algorithm

Step 1: Initialize an empty stack to store hash maps (atom counts) and push an empty hash map onto the stack.
Step 2: Iterate through the formula string character by character.
Step 3: If the current character is '(', push a new empty hash map onto the stack and increment the index.
Step 4: If the current character is ')', pop the top hash map from the stack. Parse the number following the closing parenthesis (if any) as the multiplier. Iterate through the elements in the popped hash map, multiplying each count by the multiplier and adding it to the corresponding element in the hash map at the top of the stack. Increment the index appropriately.
Step 5: If the current character is an uppercase letter, parse the element name (potentially including lowercase letters) and its count (if any). Add the element and its count to the hash map at the top of the stack. Increment the index appropriately.
Step 6: After processing the entire string, retrieve the final atom counts from the hash map at the bottom of the stack.
Step 7: Sort the elements alphabetically.
Step 8: Build the result string by iterating through the sorted elements and appending the element name and its count (if greater than 1) to the string.
Step 9: Return the result string.

Key Insights

Insight 1: The use of a stack is crucial for handling the nested parentheses and correctly applying multipliers to the atom counts within each group.
Insight 2: A hash map (or dictionary) is essential to efficiently store and update the counts of each atom as the formula is parsed.
Insight 3: The final result needs to be sorted alphabetically by element name, implying the use of sorting or a data structure that maintains sorted order (like TreeMap in Java).
Insight 4: Parsing digits from the string needs careful handling to avoid errors when multipliers or atom counts are implicitly '1'.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n)

Topics

This problem involves: Hash Table, String, Stack, Sorting.

Companies

Asked at: Confluent, Coupang, Docusign, Fastenal.

Number of Atoms | LeetCode 726

Hard

Hash Table String Stack Sorting

Time: O(n^2)Space: O(n)

Solution Code

Available in:

import java.util.Stack;
import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;

class Solution {
    public String countOfAtoms(String formula) {
        int n = formula.length();
        Stack<Map<String, Integer>> stack = new Stack<>();
        stack.push(new HashMap<>());
        int i = 0;

        while (i < n) {
            if (formula.charAt(i) == '(') {
                stack.push(new HashMap<>());
                i++;
            } else if (formula.charAt(i) == ')') {
                Map<String, Integer> top = stack.pop();
                i++;

                int i_start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplier = (i_start == i) ? 1 : Integer.parseInt(formula.substring(i_start, i));

                for (Map.Entry<String, Integer> entry : top.entrySet()) {
                    String elem = entry.getKey();
                    int count = entry.getValue();
                    stack.peek().put(elem, stack.peek().getOrDefault(elem, 0) + count * multiplier);
                }
            } else {
                int i_start = i;
                i++;
                while (i < n && Character.isLowerCase(formula.charAt(i))) {
                    i++;
                }
                String elem = formula.substring(i_start, i);

                i_start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int count = (i_start == i) ? 1 : Integer.parseInt(formula.substring(i_start, i));

                stack.peek().put(elem, stack.peek().getOrDefault(elem, 0) + count);
            }
        }

        Map<String, Integer> final_counts = stack.get(0);

        TreeMap<String, Integer> sortedAtoms = new TreeMap<>(final_counts);

        StringBuilder result = new StringBuilder();
        for (Map.Entry<String, Integer> entry : sortedAtoms.entrySet()) {
            String atom = entry.getKey();
            int count = entry.getValue();
            result.append(atom);
            if (count > 1) {
                result.append(String.valueOf(count));
            }
        }

        return result.toString();
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 726: Number of Atoms - Detailed explanation and solution approaches.

Topics

Hash Table String Stack Sorting

Companies

ConfluentCoupangDocusignFastenal

Stats

Difficulty:Hard

Languages:4

Companies:4

Problem #:726

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize an empty stack to store hash maps (atom counts) and push an empty hash map onto the stack.
2
Step 2: Iterate through the formula string character by character.
3
Step 3: If the current character is '(', push a new empty hash map onto the stack and increment the index.
4
Step 4: If the current character is ')', pop the top hash map from the stack. Parse the number following the closing parenthesis (if any) as the multiplier. Iterate through the elements in the popped hash map, multiplying each count by the multiplier and adding it to the corresponding element in the hash map at the top of the stack. Increment the index appropriately.
5
Step 5: If the current character is an uppercase letter, parse the element name (potentially including lowercase letters) and its count (if any). Add the element and its count to the hash map at the top of the stack. Increment the index appropriately.
6
Step 6: After processing the entire string, retrieve the final atom counts from the hash map at the bottom of the stack.
7
Step 7: Sort the elements alphabetically.
8
Step 8: Build the result string by iterating through the sorted elements and appending the element name and its count (if greater than 1) to the string.
9
Step 9: Return the result string.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the dominant operations: parsing the string, multiplying counts after a closing parenthesis, and sorting the final counts. The space complexity is dictated by the maximum depth of the stack and the number of unique elements stored in the hash maps.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Descent Parser

A recursive descent parser can also be used to solve this problem. This approach uses recursive functions to parse the different components of the formula.

Time: O(n + m log m)Space: O(n + m), recursion stack and the hashmap

Trade-offs: The recursive descent parser might be slightly more readable for some, but it can also be more complex to implement correctly, especially for error handling. Stack overflow may be a concern for excessively nested formulas in some languages.

✨

Key Insights

1Insight 1: The use of a stack is crucial for handling the nested parentheses and correctly applying multipliers to the atom counts within each group.
2Insight 2: A hash map (or dictionary) is essential to efficiently store and update the counts of each atom as the formula is parsed.
3Insight 3: The final result needs to be sorted alphabetically by element name, implying the use of sorting or a data structure that maintains sorted order (like TreeMap in Java).
4Insight 4: Parsing digits from the string needs careful handling to avoid errors when multipliers or atom counts are implicitly '1'.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

String

A sequence of characters. Like a word or sentence in programming!

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Formula with no multipliers, like 'H2O'. The solution correctly handles the missing multiplier by implicitly setting it to 1.
Edge case 2: Formula with single-character elements, like 'H'. The solution accurately parses the element and assigns a count of 1.
Edge case 3: Formula with deeply nested parentheses, like '((H))2'. The stack handles the nesting correctly, ensuring the multiplier is applied appropriately.
Edge case 4: Formula with zero counts is invalid based on constraints. No error checking is needed.
Edge case 5: Handling single level multiple occurences of parenthesis with different multipliers like '(H)2(O)3' - the solution correctly parses and adds the atom counts to stack[0] for final result.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly parsing the numbers following parentheses or elements. It's crucial to handle the case where no number is present, which implies a count of 1.

✗Common mistake 2: Forgetting to sort the elements alphabetically before constructing the final string.

✗Common mistake 3: Failing to properly handle the stack and correctly apply multipliers to the atom counts at different levels of nesting.

✗Common mistake 4: Memory leaks in C implementation due to not freeing dynamically allocated strings.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: This algorithm can be used in chemistry software to analyze and manipulate chemical formulas, such as calculating molar masses or balancing chemical equations.

🏦Real-world scenario 2: It can also be applied in materials science to analyze the composition of different materials.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 7, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Number of Atoms"?

For this hard-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?