Find Array after removing -1 and closest non-negative left element - Coding

Given an array arr[] of size N that contains -1 and all positive integers, the task is to modify the array and print the final array after performing the below valid operations:

Choose -1 from the array.
Remove the closest non-negative element (if there is any) to its left, as well as remove -1 itself.

Examples:

Input: arr[] = {1, 2, 3, -1, -1, 4, 5, 6, -1, 0}
Output: 1 4 5 0
Explanation: The closest element to the 1st occurrence of -1 is 3 in {1, 2, 3, -1, -1, 4, 5, 6, -1, 0}. After removing -1 and 3 arr becomes {, 2, -1, 4, 5, 6, -1, 0}.
The closest element to the 1st occurrence of -1 is 2 in {1, 2, -1, 4, 5, 6, -1, 0}. After removing -1 and 2 arr becomes {1, 4, 5, 6, -1, 0}.
The closest element to the 1st occurrence of -1 is 6 in {1, 4, 5, 6, -1, 0}. After removing -1 and 6 arr becomes {1, 4, 5, 0}.

Input: arr[] = {-1, 0, 1, -1, 10}
Output: 0 10
Explanation: There is no element exist closest in right of first occurrence of -1 in {-1, 0, 1, -1, 10}. So we will only remove -1. After removing -1 arr becomes {0, 1, -1, 10}.
The closest element to the 1st occurrence of -1 is 1 in {0, 1, -1, 10}. After removing -1 and 1 arr becomes {0, 10}

Naive Approach: The basic way to solve the problem is as follows:

Traverse on the array from left to right
Find the first occurrence of -1 and make it -10
If -1 is found then traverse on the left part and find the first non-negative integer and make it -10.
Again traverse the array to the right from where we got the first occurrence of -1 and again repeat the above two steps.

Below is the implementation for the above approach:

C++

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to remove -1 and
// corresponding left
void removeBadElements(int arr[], int n)
{
 
    // Traversing from left to right
    for (int i = 0; i < n; i++) {
 
        // If -1 occurs
        if (arr[i] == -1) {
 
            // Make -1 to -10 for
            // printing purpose
            arr[i] = -10;
 
            // Traverse from right to left
            // to get first non-negative
            // element
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] >= 0) {
                    arr[j] = -10;
                    break;
                }
            }
        }
    }
 
    // Printing array elements
    for (int i = 0; i < n; i++)
        if (arr[i] != -10)
            cout << arr[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, -1, -1, 4, 5, 6, -1, 0 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    removeBadElements(arr, N);
    return 0;
}

Java

// Java code for the above approach:
import java.util.*;
 
class GFG{
 
  // Function to remove -1 and
  // corresponding left
  static void removeBadElements(int arr[], int n)
  {
 
    // Traversing from left to right
    for (int i = 0; i < n; i++) {
 
      // If -1 occurs
      if (arr[i] == -1) {
 
        // Make -1 to -10 for
        // printing purpose
        arr[i] = -10;
 
        // Traverse from right to left
        // to get first non-negative
        // element
        for (int j = i - 1; j >= 0; j--) {
          if (arr[j] >= 0) {
            arr[j] = -10;
            break;
          }
        }
      }
    }
 
    // Printing array elements
    for (int i = 0; i < n; i++)
      if (arr[i] != -10)
        System.out.print(arr[i]+ " ");
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int arr[] = { 1, 2, 3, -1, -1, 4, 5, 6, -1, 0 };
    int N = arr.length;
 
    // Function Call
    removeBadElements(arr, N);
  }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python code for the above approach:
 
# Function to remove -1 and corresponding left
def removeBadElements(arr, n):
   
    # Traversing from left to right
    for i in range(n):
       
        # If -1 occurs
        if arr[i] is -1:
           
            # Make -1 to -10 for printing purpose
            arr[i] = -10
 
            # Traverse from right to left to get first non-negative element
            for j in range(i - 1, 0, -1):
                if arr[j] >= 0:
                    arr[j] = -10
                    break
 
    # Printing array elements
    for i in range(n):
        if arr[i] is not -10:
            print(arr[i], end=" ")
 
arr = [1, 2, 3, -1, -1, 4, 5, 6, -1, 0]
N = len(arr)
 
# Function call
removeBadElements(arr, N)
 
# This code is contributed by lokeshmvs21

C#

// C# code for the above approach
using System;
 
public class GFG {
    // Function to remove -1 and
    // corresponding left
    static void removeBadElements(int[] arr, int n)
    {
        // Traversing from left to right
        for (int i = 0; i < n; i++) {
            // If -1 occurs
            if (arr[i] == -1) {
 
                // Make -1 to -10 for
                // printing purpose
                arr[i] = -10;
 
                // Traverse from right to left
                // to get first non-negative
                // element
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[j] >= 0) {
                        arr[j] = -10;
                        break;
                    }
                }
            }
        }
 
        // Printing array elements
        for (int i = 0; i < n; i++)
            if (arr[i] != -10)
                Console.Write(arr[i] + " ");
    }
 
    // Driver code
    static void Main()
    {
        int[] arr = { 1, 2, 3, -1, -1, 4, 5, 6, -1, 0 };
        int N = arr.Length;
 
        // Function Call
        removeBadElements(arr, N);
    }
}
 
// This code is contributed by Rohit Pradhan

Javascript

// JavaScript code for the above approach:
 
// Function to remove -1 and
// corresponding left
function removeBadElements(arr, n)
{
 
  // Traversing from left to right
  for (let i = 0; i < n; i++)
  {
   
    // If -1 occurs
    if (arr[i] == -1)
    {
     
      // Make -1 to -10 for
      // printing purpose
      arr[i] = -10;
 
      // Traverse from right to left
      // to get first non-negative
      // element
      for (let j = i - 1; j >= 0; j--) {
        if (arr[j] >= 0) {
          arr[j] = -10;
          break;
        }
      }
    }
  }
  let ans = [];
   
  // Printing array elements
  for (let i = 0; i < n; i++) if (arr[i] != -10) ans.push(arr[i]);
  console.log(ans);
}
 
// Driver code
let arr = [1, 2, 3, -1, -1, 4, 5, 6, -1, 0];
let N = arr.length;
 
// Function Call
removeBadElements(arr, N);
 
// This code is contributed by ishankhandelwals.

Output

1 4 5 0

Time Complexity: O(N * N)
Auxiliary Space: O( 1 )

Efficient Approach: The idea to solve the problem is as follows:

Traverse the array from right to left. Store the count of -1 as on traversing from right to left on the array as well as if -1 encounters then we will make it as -10(for printing purposes after doing all operations). If we encounter a positive integer and if the count of -1 is greater than 0 then initialize the current element to -10 and we will decrement the count of -1 by 1. Likewise traverse the complete array.

Follow the steps to solve the problem:

Create a variable bad_count = 0, to store occurrence of -1 in array
Traverse on the array from right to left
If -1 occurs then increment bad_count and initialize the element to -10.
If -1 is not occurring but still bad_count is greater than 0 then initialize the element to -10 and decrement bad_count.
Repeat the above 2 steps until we traverse the complete array.

Below is the implementation of the above approach.

C++

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the final state of the array
void removeBadElements(int arr[], int n)
{
    // To count -1
    int bad_count = 0;
 
    // Traversing from right to left
    for (int i = n - 1; i >= 0; i--) {
 
        // If -1 occurs increment
        // bad_count
        if (arr[i] == -1) {
            bad_count++;
 
            // Initialize to -10 for
            // printing purpose
            arr[i] = -10;
        }
 
        // If element is not -1 but bad_
        // count on right is more
        // then also initialize element
        // to -10
        else if (bad_count > 0) {
            arr[i] = -10;
            bad_count--;
        }
    }
 
    for (int i = 0; i < n; i++)
        if (arr[i] != -10) {
            cout << arr[i] << " ";
        }
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, -1, -1, 4, 5, 6, -1, 0 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    removeBadElements(arr, N);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
// Function to find the final state of the array
static void removeBadElements(int arr[], int n)
{
    // To count -1
    int bad_count = 0;
 
    // Traversing from right to left
    for (int i = n - 1; i >= 0; i--) {
 
        // If -1 occurs increment
        // bad_count
        if (arr[i] == -1) {
            bad_count++;
 
            // Initialize to -10 for
            // printing purpose
            arr[i] = -10;
        }
 
        // If element is not -1 but bad_
        // count on right is more
        // then also initialize element
        // to -10
        else if (bad_count > 0) {
            arr[i] = -10;
            bad_count--;
        }
    }
 
    for (int i = 0; i < n; i++)
        if (arr[i] != -10) {
            System.out.print(arr[i] + " ");
        }
}
     
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, -1, -1, 4, 5, 6, -1, 0 };
    int N = arr.length;
 
    // Function call
    removeBadElements(arr, N);
}
}
 
// This code is contributed by sanjoy_62.

Python3

# Python code for the above approach
 
# Function to find the final state of the array
def removeBadElements(arr, n):
   
    # To count -1
    bad_count = 0
 
    # Traversing from right to left
    for i in range(n-1, -1, -1):
       
        # If -1 occurs increment bad_count
        if(arr[i] == -1):
            bad_count += 1
 
            # Initialize to -10 for printing purpose
            arr[i] = -10
 
        # If element is not -1 but bad_count on right is 
        # more then also initialize element to -10
        elif(bad_count > 0):
            arr[i] = -10
            bad_count -= 1
 
    for i in range(n):
        if(arr[i] != -10):
            print(arr[i], end=" ")
 
 
arr = [1, 2, 3, -1, -1, 4, 5, 6, -1, 0]
N = len(arr)
 
# Function call
removeBadElements(arr, N)
 
# This code is contributed by lokeshmvs21.

C#

// C# code to implement the approach
using System;
 
class GFG
{
 
  // Function to find the final state of the array
  static void removeBadElements(int[] arr, int n)
  {
    // To count -1
    int bad_count = 0;
 
    // Traversing from right to left
    for (int i = n - 1; i >= 0; i--) {
 
      // If -1 occurs increment
      // bad_count
      if (arr[i] == -1) {
        bad_count++;
 
        // Initialize to -10 for
        // printing purpose
        arr[i] = -10;
      }
 
      // If element is not -1 but bad_
      // count on right is more
      // then also initialize element
      // to -10
      else if (bad_count > 0) {
        arr[i] = -10;
        bad_count--;
      }
    }
 
    for (int i = 0; i < n; i++)
      if (arr[i] != -10) {
        Console.Write(arr[i] + " ");
      }
  }
 
  // Driver Code
  public static void Main()
  {
    int[] arr = { 1, 2, 3, -1, -1, 4, 5, 6, -1, 0 };
    int N = arr.Length;
 
    // Function call
    removeBadElements(arr, N);
  }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
    // JavaScript code for the above approach:
 
 
    // Function to find the final state of the array
    const removeBadElements = (arr, n) => {
        // To count -1
        let bad_count = 0;
 
        // Traversing from right to left
        for (let i = n - 1; i >= 0; i--) {
 
            // If -1 occurs increment
            // bad_count
            if (arr[i] == -1) {
                bad_count++;
 
                // Initialize to -10 for
                // printing purpose
                arr[i] = -10;
            }
 
            // If element is not -1 but bad_
            // count on right is more
            // then also initialize element
            // to -10
            else if (bad_count > 0) {
                arr[i] = -10;
                bad_count--;
            }
        }
 
        for (let i = 0; i < n; i++)
            if (arr[i] != -10) {
                document.write(`${arr[i]} `);
            }
    }
 
    // Driver code
 
    let arr = [1, 2, 3, -1, -1, 4, 5, 6, -1, 0];
    let N = arr.length;
 
    // Function call
    removeBadElements(arr, N);
 
// This code is contributed by rakeshsahni
 
</script>

Output

1 4 5 0

Time Complexity: O(N)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Find original Array from given Array of GCD of prefix
Count of Pairs such that modulo of product of one with their XOR and X is 1
Check if Array can be made strictly increasing by replacing element with Average of adjacents
Lexicographical smallest and largest Permutation from Array whose elements are max of Prefix
Minimize Array sum by replacing an element with GCD

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11