LTRIM for list capping in Redis - Time & Space Complexity

Time Complexity: LTRIM for list capping

O(m)

Understanding Time Complexity

We want to understand how the time it takes to trim a Redis list changes as the list gets bigger.

Specifically, how does the LTRIM command behave when keeping a list capped at a certain size?

Scenario Under Consideration

Analyze the time complexity of the following Redis commands used to cap a list size.

LPUSH mylist "new_item"
LTRIM mylist 0 99
    

This code adds a new item to the start of the list and then trims the list to keep only the first 100 items.

Identify Repeating Operations

Look for operations that repeat or scale with input size.

• Primary operation: The LTRIM command removes elements outside the specified range.
• How many times: It processes elements outside the kept range, which depends on how many items exceed the cap.

How Execution Grows With Input

The time to trim depends on how many extra items are removed beyond the cap.

Input Size (n)	Approx. Operations
100	Few or no removals if list is at cap
1,000	Removes about 900 items if trimming to 100
10,000	Removes about 9,900 items if trimming to 100

Pattern observation: The more items beyond the cap, the more work LTRIM does, growing roughly linearly with the number of removed items.

Final Time Complexity

Time Complexity: O(m)

This means the time grows linearly with the number of elements removed from the list during trimming.

Common Mistake

[X] Wrong: "LTRIM always runs in constant time regardless of list size."

[OK] Correct: LTRIM must remove all elements outside the range, so if many elements are removed, it takes more time.

Interview Connect

Understanding how commands like LTRIM scale helps you reason about performance in real systems and shows you can think about resource use clearly.

Self-Check

"What if we changed the trim range to keep more items, say 0 to 999 instead of 0 to 99? How would the time complexity change?"

Practice

1. What does the Redis command LTRIM mylist 0 9 do to the list mylist?

easy

A. Clears the entire list.

B. Removes the first 10 elements and keeps the rest.

C. Keeps only the last 10 elements of the list and removes the rest.

D. Keeps only the first 10 elements of the list and removes the rest.

Solution

1. Step 1: Understand LTRIM parameters

   The command LTRIM mylist 0 9 keeps elements from index 0 to 9 inclusive.

2. Step 2: Effect on list size

   This means only the first 10 elements remain; all others are removed.

3. Final Answer:

   Keeps only the first 10 elements of the list and removes the rest. -> Option D

4. Quick Check:

   LTRIM 0 9 keeps first 10 elements [OK]

Hint: LTRIM 0 9 means keep first 10 items only [OK]

Common Mistakes:

• Confusing start and stop indexes
• Thinking it removes first 10 instead of keeping them
• Assuming it keeps last 10 elements

2. Which of the following is the correct syntax to keep only the last 5 elements of a Redis list named tasks using LTRIM?

easy

A. LTRIM tasks -5 -1

B. LTRIM tasks 0 4

C. LTRIM tasks 5 -1

D. LTRIM tasks -1 -5

Solution

1. Step 1: Understand negative indexes in LTRIM

   Negative indexes count from the end: -1 is last element, -5 is fifth from last.

2. Step 2: Select correct range for last 5 elements

   Using LTRIM tasks -5 -1 keeps elements from fifth last to last, i.e., last 5 elements.

3. Final Answer:

   LTRIM tasks -5 -1 -> Option A

4. Quick Check:

   Negative indexes keep last elements [OK]

Hint: Use negative indexes to keep last elements [OK]

Common Mistakes:

• Using positive indexes to try to keep last elements
• Reversing negative indexes order
• Using invalid syntax with start > stop

3. Given a Redis list colors with elements ["red", "green", "blue", "yellow", "purple"], what will be the list content after executing LTRIM colors 1 3?

medium

A. ["green", "blue", "yellow"]

B. ["blue", "yellow", "purple"]

C. ["red", "green", "blue"]

D. ["yellow", "purple"]

Solution

1. Step 1: Identify indexes to keep

   LTRIM colors 1 3 keeps elements from index 1 to 3 inclusive.

2. Step 2: Extract elements at those indexes

   Indexes 1 to 3 are "green", "blue", "yellow".

3. Final Answer:

   ["green", "blue", "yellow"] -> Option A

4. Quick Check:

   LTRIM keeps specified index range [OK]

Hint: Indexes start at 0; keep elements between start and stop [OK]

Common Mistakes:

• Including element at index 0 by mistake
• Confusing index ranges
• Assuming LTRIM removes elements inside range

4. You run LTRIM mylist 5 2 on a Redis list. What will happen?

medium

A. The command will return an error due to invalid range.

B. The list will be emptied because start index is greater than stop index.

C. The list will be trimmed to elements from index 5 to 2, keeping those elements.

D. The list will remain unchanged.

Solution

1. Step 1: Understand LTRIM behavior with start > stop

   If start index is greater than stop index, Redis trims the list to empty.

2. Step 2: Apply to given command

   Since 5 > 2, LTRIM mylist 5 2 empties the list.

3. Final Answer:

   The list will be emptied because start index is greater than stop index. -> Option B

4. Quick Check:

   LTRIM with start > stop empties list [OK]

Hint: Start index must be ≤ stop; else list empties [OK]

Common Mistakes:

• Expecting an error instead of empty list
• Thinking list remains unchanged
• Assuming it keeps elements in reverse order

5. You want to keep only the most recent 20 messages in a Redis list chatlog. Which sequence of commands correctly caps the list size after adding a new message "Hello"?

hard

A. RPUSH chatlog "Hello"; LTRIM chatlog -20 0

B. RPUSH chatlog "Hello"; LTRIM chatlog 0 19

C. LPUSH chatlog "Hello"; LTRIM chatlog 0 19

D. LPUSH chatlog "Hello"; LTRIM chatlog -20 -1

Solution

1. Step 1: Understand list direction and adding new messages

   Using LPUSH adds new messages to the start (index 0), so recent messages are at the front.

2. Step 2: Use LTRIM to keep first 20 elements

   To keep the most recent 20 messages, trim to indexes 0 to 19, or equivalently LTRIM chatlog 0 19. Negative indexes also work but must match direction.

3. Step 3: Match push and trim commands

   Since LPUSH adds to front, LTRIM chatlog 0 19 keeps first 20 recent messages. LPUSH chatlog "Hello"; LTRIM chatlog -20 -1 uses LPUSH and LTRIM chatlog -20 -1, which keeps last 20 elements, but since new messages are at front, last 20 are oldest. So LPUSH chatlog "Hello"; LTRIM chatlog -20 -1 is incorrect.

4. Step 4: Correct option

   LPUSH chatlog "Hello"; LTRIM chatlog 0 19 uses LPUSH and LTRIM chatlog 0 19, which correctly keeps the 20 most recent messages at front.

5. Final Answer:

   LPUSH chatlog "Hello"; LTRIM chatlog 0 19 -> Option C

6. Quick Check:

   LPUSH + LTRIM 0 19 keeps recent 20 messages [OK]

Hint: Match push direction with LTRIM range to keep recent items [OK]

Common Mistakes:

• Using RPUSH but trimming front indexes
• Using negative indexes incorrectly with LPUSH
• Trimming wrong range causing oldest messages to stay