Capital Gain/Loss - Solution & Explanation

MediumDatabase8 min readAsked at: Meta, Robinhood

Problem Statement

Table: Stocks

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| stock_name    | varchar |
| operation     | enum    |
| operation_day | int     |
| price         | int     |
+---------------+---------+
(stock_name, operation_day) is the primary key (combination of columns with unique values) for this table.
The operation column is an ENUM (category) of type ('Sell', 'Buy')
Each row of this table indicates that the stock which has stock_name had an operation on the day operation_day with the price.
It is guaranteed that each 'Sell' operation for a stock has a corresponding 'Buy' operation in a previous day. It is also guaranteed that each 'Buy' operation for a stock has a corresponding 'Sell' operation in an upcoming day.

Write a solution to report the Capital gain/loss for each stock.

The Capital gain/loss of a stock is the total gain or loss after buying and selling the stock one or many times.

Return the result table in any order.

The result format is in the following example.

Example 1:

Input: 
Stocks table:
+---------------+-----------+---------------+--------+
| stock_name    | operation | operation_day | price  |
+---------------+-----------+---------------+--------+
| Leetcode      | Buy       | 1             | 1000   |
| Corona Masks  | Buy       | 2             | 10     |
| Leetcode      | Sell      | 5             | 9000   |
| Handbags      | Buy       | 17            | 30000  |
| Corona Masks  | Sell      | 3             | 1010   |
| Corona Masks  | Buy       | 4             | 1000   |
| Corona Masks  | Sell      | 5             | 500    |
| Corona Masks  | Buy       | 6             | 1000   |
| Handbags      | Sell      | 29            | 7000   |
| Corona Masks  | Sell      | 10            | 10000  |
+---------------+-----------+---------------+--------+
Output: 
+---------------+-------------------+
| stock_name    | capital_gain_loss |
+---------------+-------------------+
| Corona Masks  | 9500              |
| Leetcode      | 8000              |
| Handbags      | -23000            |
+---------------+-------------------+
Explanation: 
Leetcode stock was bought at day 1 for 1000$ and was sold at day 5 for 9000$. Capital gain = 9000 - 1000 = 8000$.
Handbags stock was bought at day 17 for 30000$ and was sold at day 29 for 7000$. Capital loss = 7000 - 30000 = -23000$.
Corona Masks stock was bought at day 1 for 10$ and was sold at day 3 for 1010$. It was bought again at day 4 for 1000$ and was sold at day 5 for 500$. At last, it was bought at day 6 for 1000$ and was sold at day 10 for 10000$. Capital gain/loss is the sum of capital gains/losses for each ('Buy' --> 'Sell') operation = (1010 - 10) + (500 - 1000) + (10000 - 1000) = 1000 - 500 + 9000 = 9500$.

Approach 1: Approach 1: Using a Dictionary to Track Buys and Sells

In this approach, we utilize a dictionary (or map) to store the net capital gain/loss for each stock. We iterate through the provided data, performing operations as follows:

When encountering a 'Buy', simply append the price to a list for that stock.
When encountering a 'Sell', pair it with the earliest 'Buy' found in the list and calculate the gain or loss by subtracting the buy price from the sell price.
Update the total capital gain/loss for that stock in the dictionary.

This approach ensures that we maintain accurate running totals per stock by matching sells with the earliest buys (FIFO - First In, First Out) pattern.

In the Python solution, we create a dictionary `gains` keyed by `stock_name`. Each key holds a list of prices under the `'prices'` key and a running total `'net'` gain/loss. We iterate over each row in the `stocks` list: for each 'Buy' operation, we append the price to the price list; for each 'Sell' operation, we calculate the gain/loss using the first price in the list (FIFO), remove it, and update the net gain/loss.

Code

PythonJava

Java

Complexity

Time Complexity is O(n), where n is the number of rows in the stock table, as we iterate through the list once and perform constant-time operations per row. Space Complexity is O(m), where m is the number of unique stocks in the list, since we maintain a list of prices for each stock.

Try this approach in the editor →

Approach 2: Approach 2: Sorting and Calculating Gains/Losses

In this approach, we first sort the operations based on the operation day. Then, we iterate through the sorted list and calculate the cumulative gain/loss for each stock. Here's a step-by-step breakdown:

Sort the operations by `operation_day` to ensure we process the transactions in order.
As we iterate through the sorted list, maintain a running tally of buy and sell transactions per stock.
Use a dictionary to accumulate the total gain/loss for each stock as we encounter sell operations.

This approach benefits from leveraging the sorted order of operations to systematically apply transactions in a straightforward manner.

The C++ solution first utilizes a sorting function `compare` to order the vector of stocks by the `operation_day`. As we iterate through this sorted list, two maps track buy prices and net gains. 'Buy' operations add to a queue, and 'Sell' operations calculate profits by dequeuing the matched buy price, updating the net gains cumulatively. This structure ensures that we handle first-in, first-out price matching efficiently using `std::deque`. After processing, results are collected in a vector for return.

Code

C++JavaScript

JavaScript

Complexity

Time Complexity is O(n log n) due to the sorting of the stocks by their operation day, followed by O(n) processing time. Space Complexity is O(m) where m refers to the distinct stocks, as we maintain data structures for each stock's price history.

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Using a Dictionary to Track Buys and Sells	Time Complexity is O(n), where n is the number of rows in the stock table, as we iterate through the list once and perform constant-time operations per row. Space Complexity is O(m), where m is the number of unique stocks in the list, since we maintain a list of prices for each stock.
Approach 2: Sorting and Calculating Gains/Losses	Time Complexity is O(n log n) due to the sorting of the stocks by their operation day, followed by O(n) processing time. Space Complexity is O(m) where m refers to the distinct stocks, as we maintain data structures for each stock's price history.

Video Solution

LeetCode Medium 1393 Interview SQL Question with Detailed Explanation | Practice SQL • Everyday Data Science • 6,720 views views

Watch 9 more video solutions →

Ready to solve this problem?

Practice Capital Gain/Loss with our built-in code editor and test cases.

Practice on FleetCode

Combine Two Tables

Second Highest Salary

Problem Info

DifficultyMedium

Acceptance85.3%

Approaches2

Reading time8 min

Asked at

Meta Robinhood

Practice this problem

Open in Editor

Capital Gain/Loss - Solution & Explanation

Problem Statement

Approach 1: Approach 1: Using a Dictionary to Track Buys and Sells

Code

Complexity

Approach 2: Approach 2: Sorting and Calculating Gains/Losses

Code

Complexity

Complexity Comparison

Video Solution

Ready to solve this problem?

Problem Info

Table of Contents

Capital Gain/Loss - Solution & Explanation

Problem Statement

Approach 1: Approach 1: Using a Dictionary to Track Buys and Sells

Code

Complexity

Approach 2: Approach 2: Sorting and Calculating Gains/Losses

Code

Complexity

Complexity Comparison

Video Solution

Ready to solve this problem?

Problem Info

Table of Contents

Problem Statement

Approach 1: Approach 1: Using a Dictionary to Track Buys and Sells

Code

Complexity

Approach 2: Approach 2: Sorting and Calculating Gains/Losses

Code

Complexity

Complexity Comparison

Video Solution

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents

Problem Statement

Approach 1: Approach 1: Using a Dictionary to Track Buys and Sells

Code

Complexity

Approach 2: Approach 2: Sorting and Calculating Gains/Losses

Code

Complexity

Complexity Comparison

Video Solution

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents