LPUSH and RPUSH for insertion in Redis - Time & Space Complexity

Time Complexity: LPUSH and RPUSH for insertion

O(1)

Understanding Time Complexity

When adding items to a list in Redis, it's important to know how the time it takes grows as the list gets bigger.

We want to understand how fast LPUSH and RPUSH commands work as the list grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Add elements to the start of the list
LPUSH mylist "item1"
LPUSH mylist "item2"

# Add elements to the end of the list
RPUSH mylist "item3"
RPUSH mylist "item4"
    

This code adds items to the beginning and end of a Redis list named 'mylist'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting an element at the start or end of the list.
• How many times: Each LPUSH or RPUSH command inserts one element once.

How Execution Grows With Input

Adding one item to the start or end of the list takes about the same time no matter how big the list is.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time to insert stays roughly the same even as the list grows.

Final Time Complexity

Time Complexity: O(1)

This means inserting an item at the start or end of the list takes constant time, no matter how many items are already in the list.

Common Mistake

[X] Wrong: "Adding items to the start of a list takes longer as the list grows because it has to move all the other items."

[OK] Correct: Redis lists are designed to add items at the start or end quickly without shifting all elements, so the time stays constant.

Interview Connect

Understanding how Redis handles list insertions helps you explain efficient data operations clearly and confidently in real-world situations.

Self-Check

"What if we used the LINSERT command to add an item in the middle of the list? How would the time complexity change?"

Practice

1. What does the Redis command LPUSH mylist "apple" do?

easy

A. Adds "apple" to the start (left) of the list named mylist.

B. Adds "apple" to the end (right) of the list named mylist.

C. Removes "apple" from the list named mylist.

D. Creates a new list named mylist without adding any elements.

Solution

1. Step 1: Understand LPUSH command behavior

   The LPUSH command inserts the given element(s) at the start (left) of the list.

2. Step 2: Apply to the example

   LPUSH mylist "apple" adds "apple" to the left side of the list named mylist.

3. Final Answer:

   Adds "apple" to the start (left) of the list named mylist. -> Option A

4. Quick Check:

   LPUSH = insert left [OK]

Hint: LPUSH inserts at the start (left) of the list [OK]

Common Mistakes:

• Confusing LPUSH with RPUSH and thinking it adds to the end.
• Assuming LPUSH removes elements instead of adding.
• Believing LPUSH creates a list without adding elements.

2. Which of the following is the correct syntax to add "banana" to the end of a Redis list named fruits?

easy

A. RPUSH fruits "banana"

B. LPUSH fruits "banana"

C. PUSH fruits "banana"

D. APPEND fruits "banana"

Solution

1. Step 1: Identify command to add at the end

   RPUSH adds elements to the end (right) of a Redis list.

2. Step 2: Check syntax correctness

   RPUSH fruits "banana" correctly adds "banana" to the end of the list named fruits.

3. Final Answer:

   RPUSH fruits "banana" -> Option A

4. Quick Check:

   RPUSH = insert right [OK]

Hint: RPUSH adds to the end (right) of the list [OK]

Common Mistakes:

• Using LPUSH instead of RPUSH to add at the end.
• Using non-existent commands like PUSH or APPEND.
• Incorrect command order or missing quotes.

3. Given an empty Redis list colors, what will be the result of these commands executed in order?
LPUSH colors "red"
RPUSH colors "blue"
LPUSH colors "green"
What is the content of the list colors after these commands?

medium

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

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

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

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

Solution

1. Step 1: Apply LPUSH colors "red" on empty list

   List becomes ["red"] because LPUSH adds "red" to the start.

2. Step 2: Apply RPUSH colors "blue"

   List becomes ["red", "blue"] because RPUSH adds "blue" to the end.

3. Step 3: Apply LPUSH colors "green"

   List becomes ["green", "red", "blue"] because LPUSH adds "green" to the start.

4. Final Answer:

   ["green", "red", "blue"] -> Option D

5. Quick Check:

   LPUSH adds left, RPUSH adds right [OK]

Hint: Track list from left (LPUSH) and right (RPUSH) insertions [OK]

Common Mistakes:

• Mixing order of elements after LPUSH and RPUSH.
• Assuming RPUSH adds to the start.
• Ignoring the order of commands executed.

4. You run the command LPUSH mylist "orange" "lemon" but get a "WRONGTYPE Operation against a key holding the wrong kind of value" error. What is the likely cause?

medium

A. LPUSH does not accept multiple values in one command.

B. The key mylist exists but is not a list.

C. LPUSH requires each value to be added with separate commands.

D. The correct syntax requires the key to be last.

Solution

1. Step 1: Check LPUSH command syntax

   LPUSH supports multiple values in one command and creates a list if the key does not exist.

2. Step 2: Identify the WRONGTYPE error cause

   The error occurs because the key 'mylist' already exists but holds a different data type (not a list).

3. Final Answer:

   The key mylist exists but is not a list. -> Option B

4. Quick Check:

   LPUSH + WRONGTYPE = key exists wrong type [OK]

Hint: LPUSH fails with WRONGTYPE if key exists as non-list [OK]

Common Mistakes:

• Assuming LPUSH cannot add multiple values at once.
• Thinking list must exist before LPUSH.
• Misordering command arguments.

5. You want to create a Redis list tasks with the elements ["task1", "task2", "task3"] in that exact order, where task1 is the first element and task3 is the last. Which sequence of commands will achieve this?

hard

A. LPUSH tasks "task1"; LPUSH tasks "task2"; LPUSH tasks "task3"

B. RPUSH tasks "task3"; RPUSH tasks "task2"; RPUSH tasks "task1"

C. RPUSH tasks "task1"; RPUSH tasks "task2"; RPUSH tasks "task3"

D. LPUSH tasks "task1"; RPUSH tasks "task2"; LPUSH tasks "task3"

Solution

1. Step 1: Understand desired order

   We want the list as ["task1", "task2", "task3"] with task1 first and task3 last.

2. Step 2: Choose commands to add elements in order

   RPUSH adds elements to the end, so adding task1, then task2, then task3 with RPUSH keeps the order correct.

3. Step 3: Analyze other options

   LPUSH adds to start, so LPUSH tasks "task1"; LPUSH tasks "task2"; LPUSH tasks "task3" reverses order; LPUSH tasks "task1"; RPUSH tasks "task2"; LPUSH tasks "task3" mixes commands causing wrong order; RPUSH tasks "task3"; RPUSH tasks "task2"; RPUSH tasks "task1" reverses order.

4. Final Answer:

   RPUSH tasks "task1"; RPUSH tasks "task2"; RPUSH tasks "task3" -> Option C

5. Quick Check:

   RPUSH in order = correct list order [OK]

Hint: Use RPUSH in order to keep elements in desired sequence [OK]

Common Mistakes:

• Using LPUSH in order, which reverses the list.
• Mixing LPUSH and RPUSH causing unexpected order.
• Adding elements in reverse order.