Skip to content

refactor: Refactored calculateMaxOfMin() (#5) #2957

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 2 commits into from
Closed

refactor: Refactored calculateMaxOfMin() (#5) #2957

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
0df81d5
refactor: Refactored calculateMaxOfMin() (#5)
chubretovic Feb 22, 2022
f671bec
feat: add the four test case (#5)
chubretovic Feb 22, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
24 changes: 20 additions & 4 deletions pom.xml
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,7 +12,6 @@
<maven.compiler.source>17</maven.compiler.source>
<maven.compiler.target>17</maven.compiler.target>
</properties>

<dependencyManagement>
<dependencies>
<dependency>
Expand All @@ -24,15 +23,13 @@
</dependency>
</dependencies>
</dependencyManagement>

<dependencies>
<dependency>
<groupId>org.junit.jupiter</groupId>
<artifactId>junit-jupiter</artifactId>
<scope>test</scope>
</dependency>
</dependencies>

<build>
<plugins>
<plugin>
Expand All @@ -43,6 +40,25 @@
<artifactId>maven-surefire-plugin</artifactId>
<version>2.22.2</version>
</plugin>
<plugin>
<groupId>org.jacoco</groupId>
<artifactId>jacoco-maven-plugin</artifactId>
<version>0.8.7</version>
<executions>
<execution>
<goals>
<goal>prepare-agent</goal>
</goals>
</execution>
<execution>
<id>report</id>
<phase>prepare-package</phase>
<goals>
<goal>report</goal>
</goals>
</execution>
</executions>
</plugin>
</plugins>
</build>
</project>
</project>
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
</project>
</project>

84 changes: 30 additions & 54 deletions src/main/java/com/thealgorithms/datastructures/stacks/MaximumMinimumWindow.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,7 +1,6 @@
package com.thealgorithms.datastructures.stacks;

import java.util.Arrays;
import java.util.Stack;

/**
* Given an integer array. The task is to find the maximum of the minimum of
Expand All @@ -19,7 +18,7 @@
* So in the iteration 1 the windows would be [10], [20], [30], [50], [10],
* [70], [30]. Now we need to check the minimum value in each window. Since the
* window size is 1 here the minimum element would be the number itself. Now the
* maximum out of these is the result in iteration 1. In the second iteration we
* maximum out of these is the result in iteration 1 (70). In the second iteration we
* need to consider window size 2, so there would be [10,20], [20,30], [30,50],
* [50,10], [10,70], [70,30]. Now the minimum of each window size would be
* [10,20,30,10,10] and the maximum out of these is 30. Similarly we solve for
Expand All @@ -38,59 +37,35 @@ public class MaximumMinimumWindow {
* @return result array
*/
public static int[] calculateMaxOfMin(int[] arr, int n) {
Stack<Integer> s = new Stack<>();
int left[] = new int[n + 1];
int right[] = new int[n + 1];
for (int i = 0; i < n; i++) {
left[i] = -1;
right[i] = n;
}

for (int i = 0; i < n; i++) {
while (!s.empty() && arr[s.peek()] >= arr[i]) {
s.pop();
int[] ans = new int[n];

// The first element of the result array is the maximum of the array
int[] arr2 = Arrays.copyOf(arr, arr.length);
Arrays.sort(arr2);
int maxNum = arr2[arr2.length - 1];
ans[0] = maxNum;

// Then, we follow with the size windows
int index = 1; // index of the next number to add in the ans
while (index != ans.length){
//minimus contains the minumum int of each window
int[] minimums = new int[n - index];
for (int i = 0; i < n - index; i++) {
//windowArray contains the ints of each window
int[] windowArray = Arrays.copyOfRange(arr, i, i + index + 1);
Arrays.sort(windowArray);
int minNum = windowArray[0];
minimums[i] = minNum;
}

if (!s.empty()) {
left[i] = s.peek();
}

s.push(i);
}

while (!s.empty()) {
s.pop();
}

for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && arr[s.peek()] >= arr[i]) {
s.pop();
}

if (!s.empty()) {
right[i] = s.peek();
}

s.push(i);
}

int ans[] = new int[n + 1];
for (int i = 0; i <= n; i++) {
ans[i] = 0;
}

for (int i = 0; i < n; i++) {
int len = right[i] - left[i] - 1;

ans[len] = Math.max(ans[len], arr[i]);
}

for (int i = n - 1; i >= 1; i--) {
ans[i] = Math.max(ans[i], ans[i + 1]);
}
Arrays.sort(minimums);
ans[index] = minimums[minimums.length - 1];
index += 1;
}

// Print the result
for (int i = 1; i <= n; i++) {
System.out.println();
System.out.print("ans: ");
for (int i = 0; i < n; i++) {
System.out.print(ans[i] + " ");
}
Comment on lines 65 to 70
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please remove printing the result

return ans;
Expand All @@ -100,7 +75,8 @@ public static void main(String args[]) {
int[] arr = new int[]{10, 20, 30, 50, 10, 70, 30};
int[] target = new int[]{70, 30, 20, 10, 10, 10, 10};
int[] res = calculateMaxOfMin(arr, arr.length);
assert Arrays.equals(target, res);
//assert Arrays.equals(target, res);
Comment on lines 75 to +78
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please remove main()


}

}
}
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
}
}

56 changes: 56 additions & 0 deletions src/test/java/com/thealgorithms/datastructures/stacks/MaximumMinimumWindowTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,56 @@
package com.thealgorithms.datastructures.stacks;

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.BeforeAll;
import static org.junit.jupiter.api.Assertions.*;

import java.util.*;


public class MaximumMinimumWindowTest {

static MaximumMinimumWindow MMW;

@BeforeAll
static void startUp(){
MMW = new MaximumMinimumWindow();
}

//Check a basic test
@Test
public void checkBasicCase(){
int[] arr = new int[]{10, 20, 30, 50, 10, 70, 30};
int[] target = new int[]{70, 30, 20, 10, 10, 10, 10};
int[] res = MaximumMinimumWindow.calculateMaxOfMin(arr, arr.length);
assert Arrays.equals(target, res);
}

//Check a basic false test
@Test
public void checkBasicFakeCase(){
int[] arr = new int[]{10, 20, 30, 50, 10, 70, 30};
int[] fake_target = new int[]{10, 20, 30, 50, 10, 70, 30};
int[] res = MaximumMinimumWindow.calculateMaxOfMin(arr, arr.length);
boolean answer = Arrays.equals(fake_target, res);
assertFalse(answer);
}

//Check an array full of identical numbers
@Test
public void checkAnArrayFullOfIdenticalNumbers(){
int[] arr = new int[]{10, 10, 10, 10, 10, 10, 10};
int[] target = new int[]{10, 10, 10, 10, 10, 10, 10};
int[] res = MaximumMinimumWindow.calculateMaxOfMin(arr, arr.length);
assert Arrays.equals(target, res);
}

//Check when the window is lower than the array's length
@Test
public void checkWindowLower(){
int[] arr = new int[]{10, 20, 30, 50, 10, 70, 30};
int[] target = new int[]{70, 10};
int[] res = MaximumMinimumWindow.calculateMaxOfMin(arr, 2);
assert Arrays.equals(target, res);
}

}