Computer Science, asked by jothis4274, 11 months ago

Given a sorted array, remove the duplicates in place such that each element can appear atmost twice and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.

Answers

Answered by frozenPearl93
1

LLICODER

Golang

Kotlin

Java

Spring Boot

Node.js

System Design

DevOps

Algorithms

About

Remove duplicates from sorted array II

Algorithms • Nov 3, 2019 • 2 mins read

Remove Duplicates from Sorted Array II

Given a sorted array, remove the duplicates from the array in-place such that each element appears at most twice, and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array 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]

Remove Duplicates from Sorted Array II solution in Java

This problem is an extension of the problem Remove duplicates from Sorted Array

It can also be solved in O(n) time complexity by using two pointers (indexes).

class RemoveDuplicatesSortedArrayII {

private static int removeDuplicates(int[] nums) {

int n = nums.length;

/*

* This index will move when we modify the array in-place to include an element

* so that it is not repeated more than twice.

*/

int j = 0;

for (int i = 0; i < n; i++) {

/*

* If the current element is equal to the element at index i+2, then skip the

* current element because it is repeated more than twice.

*/

if (i < n - 2 && nums[i] == nums[i + 2]) {

continue;

}

nums[j++] = nums[i];

}

return j;

}

public static void main(String[] args) {

int[] nums = new int[] { 1, 1, 1, 3, 5, 5, 7 };

int newLength = removeDuplicates(nums);

System.out.println("Length of array after removing duplicates = " + newLength);

System.out.print("Array = ");

for (int i = 0; i < newLength; i++) {

System.out.print(nums[i] + " ");

}

System.out.println();

}

}

Similar questions