Replacing adjacent opposite sign pairs with their absolute max in an array

Given an array arr[] of size n, the task is to find the final array by repeatedly performing the following operations if two elements of opposite signs are adjacent:

• Remove both opposite signed elements from the maximumarray and insert the element having maximum absolute value along with its sign.
• If both the elements have the same absolute value, both will be removed from the array.

Examples:

Input: arr[] = [10, -5, -8, 2, -5]
Output: [10]
Explanation: 
At Index 0 : Element 10 has positive sign.
At Index 1 : -5  has lesser absolute value than 10. Replace both of them with 10.
At Index 2 : -8  has lesser absolute value than 10. Replace both of them with 10.
At Index 3 : 2 has positive sign. So it will be in the array.
At Index 4 : -5  has greater absolute value than 2. Replace both of them with 5.
Now -5  has lesser absolute value than 10. Replace both of them with 10.

Input: arr[] = [5, -5, -2, -10]
Output: [-2, -10]
Explanation: 1st and 2nd element gets discarded because both elements have same values but opposite sign. 3rd and 4th elements have same sign. So, both will be in the array.

This approach uses a stack to process an array by handling adjacent opposite sign pairs. Positive elements are pushed directly onto the stack, while negative elements are compared with the stack's top. If the top is a smaller positive element, it is popped. If the negative element and the top have the same absolute value, both are discarded. If the stack is empty or the top is negative, the negative element is pushed onto the stack. The stack then holds the remaining valid elements, which are returned as the reduced array.

Steps:

1. Initialize a stack to hold the array elements.

2. Traverse the array:

If the element is positive, push it directly onto the stack.

If the element is negative, do the following:

• Pop smaller positive elements from the stack, where their absolute value is less than the current element.
• If the top of the stack and the current element have the same absolute value (opposite signs), pop the top of the stack.
• If the stack is empty or the top element is negative, push the current negative element onto the stack.

3. Return the stack with the remaining elements after processing all elements in the array.

#include <iostream>
#include <vector>
using namespace std;

vector<int> reduceArray(vector<int>& arr) {

    // Stack to store elements
    vector<int> s;

    // Traverse entire array
    for (int i = 0; i < arr.size(); i++) {
        int element = arr[i];

        // If positive element, directly push into stack
        if (element >= 0)
            s.push_back(element);

        else {
            // Pop all smaller elements moving in the right direction
            while (s.size() > 0 && s.back() >= 0 && abs(element) > s.back())
                s.pop_back();

            // Top of stack and current element have the same value and 
            // top of stack is moving in the right direction
            if (s.size() > 0 && s.back() >= 0 && s.back() == abs(element))
                s.pop_back();

            // No more elements remaining or remaining elements moving in the left direction
            else if (s.size() == 0 || s.back() < 0)
                s.push_back(element);
        }
    }

    return s;
}

int main() {
    vector<int> arr = {10, -5, -8, 2, -5};  

    vector<int> result = reduceArray(arr);  

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }

    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class GfG {
    public static List<Integer> reduceArray(List<Integer> arr) {
        // Stack to store elements
        List<Integer> s = new ArrayList<>();

        // Traverse entire array
        for (int element : arr) {
            // If positive element, directly push into stack
            if (element >= 0)
                s.add(element);
            else {
                // Pop all smaller elements moving in the right direction
                while (s.size() > 0 && s.get(s.size() - 1) >= 0 && Math.abs(element) > s.get(s.size() - 1))
                    s.remove(s.size() - 1);

                // Top of stack and current element have the same value and 
                // top of stack is moving in the right direction
                if (s.size() > 0 && s.get(s.size() - 1) >= 0 && s.get(s.size() - 1) == Math.abs(element))
                    s.remove(s.size() - 1);

                // No more elements remaining or remaining elements moving in the left direction
                else if (s.size() == 0 || s.get(s.size() - 1) < 0)
                    s.add(element);
            }
        }

        return s;
    }

    public static void main(String[] args) {
        List<Integer> arr = List.of(10, -5, -8, 2, -5);

        List<Integer> result = reduceArray(arr);

        for (int value : result) {
            System.out.print(value + " ");
        }
    }
}

def reduce_array(arr):
    # Stack to store elements
    s = []

    # Traverse entire array
    for element in arr:
        # If positive element, directly push into stack
        if element >= 0:
            s.append(element)
        else:
            # Pop all smaller elements moving in the right direction
            while s and s[-1] >= 0 and abs(element) > s[-1]:
                s.pop()

            # Top of stack and current element have the same value and 
            # top of stack is moving in the right direction
            if s and s[-1] >= 0 and s[-1] == abs(element):
                s.pop()

            # No more elements remaining or remaining elements moving in the left direction
            elif not s or s[-1] < 0:
                s.append(element)
    return s

if __name__ == '__main__':
    arr = [10, -5, -8, 2, -5]
    result = reduce_array(arr)
    print(' '.join(map(str, result)))

using System;
using System.Collections.Generic;

class GfG {
    static List<int> ReduceArray(List<int> arr) {
        // Stack to store elements
        List<int> s = new List<int>();

        // Traverse entire array
        foreach (int element in arr) {
            // If positive element, directly push into stack
            if (element >= 0)
                s.Add(element);
            else {
                // Pop all smaller elements moving in the right direction
                while (s.Count > 0 && s[s.Count - 1] >= 0 && Math.Abs(element) > s[s.Count - 1])
                    s.RemoveAt(s.Count - 1);

                // Top of stack and current element have the same value and 
                // top of stack is moving in the right direction
                if (s.Count > 0 && s[s.Count - 1] >= 0 && s[s.Count - 1] == Math.Abs(element))
                    s.RemoveAt(s.Count - 1);

                // No more elements remaining or remaining elements moving in the left direction
                else if (s.Count == 0 || s[s.Count - 1] < 0)
                    s.Add(element);
            }
        }

        return s;
    }

    static void Main() {
        List<int> arr = new List<int> { 10, -5, -8, 2, -5 };
        List<int> result = ReduceArray(arr);

        foreach (int value in result) {
            Console.Write(value + " ");
        }
    }
}

function reduceArray(arr) {
    // Stack to store elements
    let s = [];

    // Traverse entire array
    for (let element of arr) {
        // If positive element, directly push into stack
        if (element >= 0)
            s.push(element);
        else {
            // Pop all smaller elements moving in the right direction
            while (s.length > 0 && s[s.length - 1] >= 0 && Math.abs(element) > s[s.length - 1])
                s.pop();

            // Top of stack and current element have the same value and 
            // top of stack is moving in the right direction
            if (s.length > 0 && s[s.length - 1] >= 0 && s[s.length - 1] === Math.abs(element))
                s.pop();

            // No more elements remaining or remaining elements moving in the left direction
            else if (s.length === 0 || s[s.length - 1] < 0)
                s.push(element);
        }
    }

    return s;
}

const arr = [10, -5, -8, 2, -5];
const result = reduceArray(arr);
console.log(result.join(' '));

10 

Time Complexity: O(n)
Auxiliary Space: O(n)