What is the time complexity of Design Circular Queue?

The optimal solution has a time complexity of O(1).

What data structures are used to solve Design Circular Queue?

This problem uses Array, Linked List, Design, Queue. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Design Circular Queue?

Insight 1: The key to implementing a circular queue efficiently is using the modulo operator (%) to handle the wrap-around effect when the head or tail reaches the end of the underlying array. Insight 2: To distinguish between an empty and a full queue when both the head and tail are at the same position, it's useful to allocate one extra space in the underlying array. This allows us to determine fullness by checking if `(tail + 1) % capacity == head`.

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

Design Circular Queue - LeetCode 622 Solution

Q: Which companies ask LeetCode 622. Design Circular Queue in interviews?

This problem is frequently asked at Applied Intuition, Citadel, Cloudflare, Datadog, Intuit and 3 more companies.

Design Circular Queue - Complete Solution Guide

Design Circular Queue is LeetCode problem 622, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer". One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a spa

Detailed Explanation

The problem asks us to implement a circular queue data structure without using built-in queue classes. A circular queue is a queue that reuses space at the beginning of the queue after elements are dequeued. It behaves like a regular FIFO (First-In, First-Out) queue, but when the 'tail' reaches the end of the allocated space, it wraps around to the beginning, effectively using the available empty slots. We need to implement methods for initialization, enqueue (add element), dequeue (remove element), get front element, get rear element, check if the queue is empty, and check if the queue is full.

Solution Approach

The solution uses an array to store the queue elements, along with two pointers, `head` and `tail`, to track the front and rear of the queue. The `capacity` of the queue is initialized to `k + 1`, where `k` is the specified queue size, to differentiate between empty and full states. The modulo operator (%) is used extensively to ensure that the `head` and `tail` wrap around the array when they reach the end. The `enQueue` operation adds an element at the `tail` position and increments `tail` using modulo. The `deQueue` operation increments the `head` using modulo. `Front` and `Rear` return the elements at the `head` and `tail - 1` positions, respectively. `isEmpty` and `isFull` check the conditions based on the positions of `head` and `tail`.

Step-by-Step Algorithm

Step 1: **Initialization (MyCircularQueue(k))**: Create an array of size `k + 1`, initialize `head` and `tail` to 0, and set `capacity` to `k + 1`.
Step 2: **Enqueue (enQueue(value))**: If the queue is full, return `false`. Otherwise, add the `value` at `queue[tail]`, and update `tail` as `tail = (tail + 1) % capacity`. Return `true`.
Step 3: **Dequeue (deQueue())**: If the queue is empty, return `false`. Otherwise, increment `head` as `head = (head + 1) % capacity`. Return `true`.
Step 4: **Front (Front())**: If the queue is empty, return -1. Otherwise, return `queue[head]`.
Step 5: **Rear (Rear())**: If the queue is empty, return -1. Otherwise, calculate the rear index as `rear_index = (tail - 1 + capacity) % capacity` and return `queue[rear_index]`.
Step 6: **IsEmpty (isEmpty())**: Return `true` if `head == tail`, and `false` otherwise.
Step 7: **IsFull (isFull())**: Return `true` if `(tail + 1) % capacity == head`, and `false` otherwise.

Key Insights

Insight 1: The key to implementing a circular queue efficiently is using the modulo operator (%) to handle the wrap-around effect when the head or tail reaches the end of the underlying array.
Insight 2: To distinguish between an empty and a full queue when both the head and tail are at the same position, it's useful to allocate one extra space in the underlying array. This allows us to determine fullness by checking if `(tail + 1) % capacity == head`.
Insight 3: Implementing the `Rear()` method requires handling the case where the `tail` is 0 (meaning it has wrapped around), requiring an adjustment to calculate the correct index using `(tail - 1 + capacity) % capacity`.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(k)

Topics

This problem involves: Array, Linked List, Design, Queue.

Companies

Asked at: Applied Intuition, Citadel, Cloudflare, Datadog, Intuit, Qualcomm, Tesla, Zoox.

Design Circular Queue | LeetCode 622

Medium

Array Linked List Design Queue

Time: O(1)Space: O(k)

Solution Code

Available in:

class MyCircularQueue {

    private int[] queue;
    private int head;
    private int tail;
    private int capacity;

    public MyCircularQueue(int k) {
        this.queue = new int[k + 1];
        this.head = 0;
        this.tail = 0;
        this.capacity = k + 1;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        this.queue[this.tail] = value;
        this.tail = (this.tail + 1) % this.capacity;
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        this.head = (this.head + 1) % this.capacity;
        return true;
    }
    
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return this.queue[this.head];
    }
    
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // The tail points to the next available slot, so the last element is at tail - 1
        // We add capacity and take modulo to handle the case where tail is 0
        int rear_index = (this.tail - 1 + this.capacity) % this.capacity;
        return this.queue[rear_index];
    }
    
    public boolean isEmpty() {
        return this.head == this.tail;
    }
    
    public boolean isFull() {
        // The queue is full if the next position for tail is the current head
        return (this.tail + 1) % this.capacity == this.head;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 622: Design Circular Queue - Detailed explanation and solution approaches.

Topics

Array Linked List Design Queue

Companies

Applied IntuitionCitadelCloudflareDatadogIntuitQualcommTeslaZoox

Stats

Difficulty:Medium

Languages:4

Companies:8

Problem #:622

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

7 steps

1
Step 1: **Initialization (MyCircularQueue(k))**: Create an array of size `k + 1`, initialize `head` and `tail` to 0, and set `capacity` to `k + 1`.
2
Step 2: **Enqueue (enQueue(value))**: If the queue is full, return `false`. Otherwise, add the `value` at `queue[tail]`, and update `tail` as `tail = (tail + 1) % capacity`. Return `true`.
3
Step 3: **Dequeue (deQueue())**: If the queue is empty, return `false`. Otherwise, increment `head` as `head = (head + 1) % capacity`. Return `true`.
4
Step 4: **Front (Front())**: If the queue is empty, return -1. Otherwise, return `queue[head]`.
5
Step 5: **Rear (Rear())**: If the queue is empty, return -1. Otherwise, calculate the rear index as `rear_index = (tail - 1 + capacity) % capacity` and return `queue[rear_index]`.
6
Step 6: **IsEmpty (isEmpty())**: Return `true` if `head == tail`, and `false` otherwise.
7
Step 7: **IsFull (isFull())**: Return `true` if `(tail + 1) % capacity == head`, and `false` otherwise.

💡

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(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(k)

📝

Why?

The time complexity is O(1) because all the operations involve simple assignments, comparisons, and modulo operations, all of which take constant time. The space complexity is O(k) because the code allocates an array of size `k + 1` to store the elements of the circular queue. The '+ 1' allows us to differentiate between the full and empty state.

📖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

Linked List Implementation

A circular queue can also be implemented using a linked list. The last node points to the first node, creating a circular structure.

Time: O(1) for all operations.Space: O(k), where k is the size of the queue.

Trade-offs: Linked list implementation might have slightly higher overhead due to node allocation and pointer manipulation, but it can be more flexible in terms of dynamic resizing if the size is not known in advance. Array implementation is generally faster due to contiguous memory allocation and simpler indexing.

✨

Key Insights

1Insight 1: The key to implementing a circular queue efficiently is using the modulo operator (%) to handle the wrap-around effect when the head or tail reaches the end of the underlying array.
2Insight 2: To distinguish between an empty and a full queue when both the head and tail are at the same position, it's useful to allocate one extra space in the underlying array. This allows us to determine fullness by checking if `(tail + 1) % capacity == head`.
3Insight 3: Implementing the `Rear()` method requires handling the case where the `tail` is 0 (meaning it has wrapped around), requiring an adjustment to calculate the correct index using `(tail - 1 + capacity) % capacity`.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Queue

FIFO structure - First In, First Out. Like a line at a store!

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: **Empty queue**: When the queue is empty, `Front()` and `Rear()` should return -1, and `deQueue()` should return `false`. The code handles this by checking `head == tail` before proceeding.
Edge case 2: **Full queue**: When the queue is full, `enQueue()` should return `false`. The code handles this by checking `(tail + 1) % capacity == head` before proceeding.
Edge case 3: **Rear element when tail is 0**: When the tail is 0, the rear index calculation `(tail - 1 + capacity) % capacity` ensures a correct negative indexing prevention, correctly wrapping to the last element.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: **Incorrectly calculating the rear index**: Forgetting to handle the case where the tail has wrapped around to the beginning (tail == 0) leads to incorrect rear index calculation.

✗Common mistake 2: **Not allocating an extra space to distinguish between empty and full states**: Without the extra space, it's impossible to differentiate between an empty queue (head == tail) and a full queue (where the tail has caught up to the head after wrapping around).

✗Common mistake 3: **Forgetting to use the modulo operator**: Failing to use the modulo operator when incrementing the head and tail pointers will cause them to go out of bounds of the array, leading to incorrect behavior.

✅

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: **Operating Systems**: Circular queues are often used in operating systems for managing process scheduling or buffering data between different parts of the system. For example, buffering audio or video data.

🏦Real-world scenario 2: **Networking**: Circular queues are used in network routers and switches for managing packets. They help ensure that packets are processed in the correct order and prevent buffer overflows.

🎮Real-world scenario 3: **Audio/Video streaming**: Buffering data to ensure smooth playback despite network jitter is another typical use case.

💡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

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

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: August 22, 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

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

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

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 "Design Circular Queue"?

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

🤖 Need help with this problem?