🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we will solve the problem of removing duplicates from a sorted array. Unlike the traditional problem where each element can only appear once, in this variant, each element is allowed to appear at most twice.
Problem
Given a sorted array, remove the duplicates such that each element can appear at most twice, and return the new length. The operation must be done in place with O(1) extra memory.
Example:
Given array [1, 1, 1, 3, 5, 5, 7]
The output should be 6, with the first six elements of the array being [1, 1, 3, 5, 5, 7]
2. Solution Steps
1. Initialize a counter (count) to track the number of times a particular element has appeared.
2. Initialize a pointer (index) to track the position in the array where the next unique element should be placed.
3. Iterate through the array, starting from the first element.
4. For each element, increment count if it's the same as the previous one; otherwise, reset count to 1.
5. If count is less than or equal to 2, update the array at index with the current element and increment index.
6. Continue this process until the end of the array.
7. Return index as the new length of the array.
3. Code Program
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] nums = {1, 1, 1, 3, 5, 5, 7};
int newLength = removeDuplicates(nums);
System.out.println("New length: " + newLength);
for (int i = 0; i < newLength; i++) {
System.out.print(nums[i] + " ");
}
}
// Method to remove duplicates such that each element appears at most twice
public static int removeDuplicates(int[] nums) {
if (nums.length <= 2) return nums.length;
int index = 1; // Start from the second element
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
count++;
} else {
count = 1;
}
if (count <= 2) {
nums[index] = nums[i]; // Update the array with the element
index++;
}
}
return index; // New length of the array
}
}
Output:
New length: 6 1 1 3 5 5 7
Explanation:
In the given array [1, 1, 1, 3, 5, 5, 7], the removeDuplicates method allows each unique element to appear at most twice. It iterates through the array, counting the occurrences of each element and updating the array in-place. The new length of the array is 6, representing the elements [1, 1, 3, 5, 5, 7], where each element appears no more than twice.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment