What is the time complexity of Remove Duplicates from Sorted Array II?

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

What data structures are used to solve Remove Duplicates from Sorted Array II?

This problem uses Array, Two Pointers. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Remove Duplicates from Sorted Array II?

Insight 1: The sorted nature of the array is crucial, allowing us to use a two-pointer approach to efficiently identify and overwrite elements in-place. Insight 2: We only need to check if the current element is greater than the element two positions before the current write position (`k - 2`). This condition determines whether to accept the current element for inclusion.

Which companies ask LeetCode 80. Remove Duplicates from Sorted Array II in interviews?

This problem is frequently asked at Accolite, Adobe, Amazon, Apple, Bloomberg and 9 more companies.

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

Remove Duplicates from Sorted Array II - LeetCode 80 Solution

Remove Duplicates from Sorted Array II - Complete Solution Guide

Remove Duplicates from Sorted Array II is LeetCode problem 80, 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

Given an integer array nums sorted in non-decreasing order , remove some duplicates in-place such that each unique element appears at most twice . The relative order of the elements should be kept the same . Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums . More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. I

Detailed Explanation

The problem requires you to remove duplicate elements from a sorted integer array `nums` in-place, such that each unique element appears at most twice. The goal is to modify the original array so that the first `k` elements contain the desired result, and then return `k`. Elements beyond `k` don't matter. We are given that the array is sorted in non-decreasing order and we need to do this with O(1) extra space.

Solution Approach

The provided solution uses a single pass through the array with a 'k' pointer that represents the index of the next available position in the modified array. For each element, it checks if `k < 2` (to handle the first two occurrences of any number) or if the current number is greater than the number two positions behind 'k' (`nums[k - 2]`). If either condition is true, it means the current number should be included, so it's written to `nums[k]` and 'k' is incremented. This approach efficiently maintains the required order while ensuring no more than two occurrences of each element.

Step-by-Step Algorithm

Step 1: Initialize `k = 0`. `k` will track the index of the next valid element to be placed in the modified array.
Step 2: Iterate through the input array `nums` using a `for` loop (or equivalent).
Step 3: For each element `num` in `nums`, check if `k < 2` or `num > nums[k - 2]`.
Step 4: If the condition in Step 3 is true, it means the current number `num` should be included in the modified array.
Step 5: If Step 4 is true, then write `num` to `nums[k]`.
Step 6: Increment `k` by 1 after writing `num` to `nums[k]`.
Step 7: After iterating through all elements in `nums`, return `k`. `k` represents the number of valid elements in the modified array, as well as the effective length of the result.

Key Insights

Insight 1: The sorted nature of the array is crucial, allowing us to use a two-pointer approach to efficiently identify and overwrite elements in-place.
Insight 2: We only need to check if the current element is greater than the element two positions before the current write position (`k - 2`). This condition determines whether to accept the current element for inclusion.
Insight 3: The 'k' variable effectively tracks the index where the next non-duplicate (or acceptable duplicate) element should be written to.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers.

Companies

Asked at: Accolite, Adobe, Amazon, Apple, Bloomberg, Meta, Microsoft, Nykaa, TikTok, Uber, Yahoo, Yandex, Zoho, tcs.

Remove Duplicates from Sorted Array II | LeetCode 80

Medium

Array Two Pointers

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        for (int num : nums) {
            if (k < 2 || num > nums[k - 2]) {
                nums[k] = num;
                k++;
            }
        }
        return k;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 80: Remove Duplicates from Sorted Array II - Detailed explanation and solution approaches.

Topics

Array Two Pointers

Companies

AccoliteAdobeAmazonAppleBloombergMetaMicrosoftNykaa

Stats

Difficulty:Medium

Languages:4

Companies:14

Problem #:80

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: Initialize `k = 0`. `k` will track the index of the next valid element to be placed in the modified array.
2
Step 2: Iterate through the input array `nums` using a `for` loop (or equivalent).
3
Step 3: For each element `num` in `nums`, check if `k < 2` or `num > nums[k - 2]`.
4
Step 4: If the condition in Step 3 is true, it means the current number `num` should be included in the modified array.
5
Step 5: If Step 4 is true, then write `num` to `nums[k]`.
6
Step 6: Increment `k` by 1 after writing `num` to `nums[k]`.
7
Step 7: After iterating through all elements in `nums`, return `k`. `k` represents the number of valid elements in the modified array, as well as the effective length of the result.

💡

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

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is linear because each element in the input array is processed a fixed number of times. The space complexity is constant because the algorithm operates in-place, meaning it does not require additional memory that scales with the size of the input. Only a single integer variable, 'k', is used for indexing, resulting in O(1) auxiliary space.

📖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

Using Collections.frequency (Java)

In Java, one could iterate through the array and use `Collections.frequency` to count occurrences of each number. This approach is less efficient due to repeated calls to `frequency`.

Time: O(n^2) in worst case where Collections.frequency is O(n) for each elementSpace: O(1)

Trade-offs: Much less efficient than the two-pointer approach. Not recommended. The provided solution is superior as it leverages the fact that the array is already sorted.

✨

Key Insights

1Insight 1: The sorted nature of the array is crucial, allowing us to use a two-pointer approach to efficiently identify and overwrite elements in-place.
2Insight 2: We only need to check if the current element is greater than the element two positions before the current write position (`k - 2`). This condition determines whether to accept the current element for inclusion.
3Insight 3: The 'k' variable effectively tracks the index where the next non-duplicate (or acceptable duplicate) element should be written to.

📚

Key Terms Explained

For Students

Array

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

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Edge Cases

Edge case 1: Empty array or array with one element. The code handles these cases correctly because the loop won't execute or it will execute once, returning 0 or 1, respectively.
Edge case 2: Array with all duplicate elements, e.g., `[1, 1, 1, 1, 1]`. The algorithm will correctly reduce it to `[1, 1]` and return 2.
Edge case 3: Array with no duplicate elements. The algorithm will process it correctly without any modifications.
Edge case 4: Array where duplicates are separated by unique numbers, e.g. [1,1,2,2,3,3]. The algorithm correctly keeps two of each number.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering the edge case where the first two elements should always be included.

✗Common mistake 2: Using additional data structures (e.g., hash maps) which violate the in-place requirement and increase space complexity.

✗Common mistake 3: Not handling the case correctly when k < 2, leading to incorrect results for the initial elements.

✅

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: Data compression. Removing duplicate data entries, allowing a controlled redundancy (up to 2 times) to maintain data integrity.

🏦Real-world scenario 2: Database indexing. When creating an index on a sorted column, limiting the number of duplicate entries can optimize storage space and search performance.

🎮Real-world scenario 3: Log processing. Analyzing log files where multiple similar events may occur close together, and you want to reduce the noise while still retaining a representative sample of the activity.

💡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

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

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

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

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 20, 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

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

❓

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.

When is the two-pointer technique most effective?

Two pointers work best on sorted arrays or when searching for pairs/triplets that satisfy a condition. Common patterns include: moving pointers inward from both ends (like in two-sum variants), fast/slow pointers for cycle detection, or left/right pointers for partitioning.

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 "Remove Duplicates from Sorted Array II"?

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 two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?