How do you solve Capital Gain/Loss on LeetCode?

Capital Gain/Loss (LeetCode #1393) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Each 'Sell' operation must correspond to a previous 'Buy' operation.

What is the brute force solution for Capital Gain/Loss?

The brute force approach for Capital Gain/Loss is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves iterating through each stock's transactions and calculating the gain or loss by matching each 'Buy' with its corresponding 'Sell'. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Capital Gain/Loss?

Capital Gain/Loss uses the following concepts: Database. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Capital Gain/Loss?

Clarify assumptions about the input data. Think about edge cases, such as multiple buys and sells for the same stock. Practice explaining your thought process while coding.

What are common mistakes when solving Capital Gain/Loss?

Not pairing 'Buy' and 'Sell' correctly, leading to incorrect calculations. Forgetting to pop the last 'Buy' price after a 'Sell'.

#1393

Capital Gain/Loss

Medium

DatabaseHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a single pass through the data, leveraging a stack to keep track of buy prices. This allows us to efficiently calculate gains/losses without the need for nested loops.

⚙️

Algorithm

3 steps

1Step 1: Initialize a dictionary to store total gain/loss for each stock.
2Step 2: Use a stack to keep track of buy prices for each stock.
3Step 3: For each transaction, if it's a 'Buy', push the price onto the stack; if it's a 'Sell', pop the last buy price and calculate the gain/loss.

solution.py14 lines

1def calculate_capital_gain(stocks):
2    gain_loss = {}
3    buy_prices = {}
4    for stock in stocks:
5        name, operation, day, price = stock
6        if operation == 'Buy':
7            if name not in buy_prices:
8                buy_prices[name] = []
9            buy_prices[name].append(price)
10        elif operation == 'Sell':
11            if name not in gain_loss:
12                gain_loss[name] = 0
13            gain_loss[name] += price - buy_prices[name].pop()  # pop last buy price
14    return gain_loss

ℹ

Complexity note: The time complexity is O(n) because we only iterate through the list of transactions once. The space complexity is O(n) due to the storage of buy prices in a stack for each stock.

1Each 'Sell' operation must correspond to a previous 'Buy' operation.
2Using a stack allows for efficient tracking of prices.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.