Test results - Codility

Tasks Details

medium

1. RectanglesStrip

From a given set choose as many rectangles with a common side as possible.

Task Score

100%

Correctness

100%

Performance

100%

There are N rectangles numbered from 0 to N-1. The K-th rectangle has size A[K] × B[K].

We want to arrange as many rectangles as possible into a strip. The rectangles can be arranged into a strip if they all share a side of the same length (which becomes the height of the strip). Note that rectangles can be rotated.

Write a function:

class Solution { public int solution(int[] A, int[] B); }

that, given two arrays A and B of N integers each, returns the maximum number of rectangles that can be arranged into a strip.

Examples:

1. Given A = [2, 3, 2, 3, 5] and B = [3, 4, 2, 4, 2], the function should return 3. Choosing the 0th, 2nd and 4th rectangles we can obtain the following strip of height 2 (note that the 0th rectangle was rotated):

(3 × 2), (2 × 2), (5 × 2)

We can also choose the 0th, 1st and 3rd rectangles to obtain a strip of height 3. Here we have rotated 1st and 3rd rectangles:

(2 × 3), (4 × 3), (4 × 3)

2. Given A = [2, 3, 1, 3] and B = [2, 3, 1, 3], the function should return 2. We can choose the 1st and 3rd rectangles:

(3 × 3), (3 × 3)

3. Given A = [2, 10, 4, 1, 4] and B = [4, 1, 2, 2, 5], the function should return 3. We can choose the 0th, 2nd and 4th rectangles to obtain a strip of height 4:

(2 × 4), (2 × 4), (5 × 4)

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

arrays A and B both consist of N integers;

each element of arrays A and B is an integer within the range [1..1,000,000,000].

Solution

Programming language used Java 21

Time spent on task 1 minutes

Notes

not defined yet

Code: 18:03:58 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A, int[] B) {
        // write your code in Java SE 8
    }
}

Code: 18:04:09 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");


class Solution {
  public int solution(int[] A, int[] B) {
    // write your code in Java SE 8
    List<Rect> list = new ArrayList<>();


    for (int i = 0; i < A.length; i++) {
      Rect opt1 = new Rect(A[i], B[i]);
      Rect opt2 = new Rect(B[i], A[i]);
      if (opt1.equals(opt2)) {
        list.add(opt1);
      } else {
        list.add(opt1);
        list.add(opt2);
      }
    }

    int heightCount = getCounter(list, "height");
    int widthCount = getCounter(list, "width");
    if (heightCount > widthCount) {
      return heightCount;
    } else if (widthCount > heightCount) {
      return widthCount;
    } else if (heightCount == widthCount && heightCount == 1) {
      return heightCount + widthCount;
    }
    return heightCount;
  }

  private static int getCounter(final List<Rect> sortedList, String type) {
    Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
    int counter = 0;
    if ("height".equals(type)) {
      for (Rect rec : sortedList) {
        if (!countMap.containsKey(rec.height)) {
          countMap.put(rec.height, 1);
          if (counter == 0) {
            counter = 1;
          }
        } else {
          int tempCounter = countMap.get(rec.height) + 1;
          if (tempCounter > counter)
            counter = tempCounter;
          countMap.replace(rec.height, tempCounter);
        }
      }
    } else if ("width".equals(type)) {
      for (Rect rec : sortedList) {
        if (!countMap.containsKey(rec.width)) {
          countMap.put(rec.width, 1);
          if (counter == 0) {
            counter = 1;
          }
        } else {
          int tempCounter = countMap.get(rec.width) + 1;
          if (tempCounter > counter)
            counter = tempCounter;
          countMap.replace(rec.width, tempCounter);
        }
      }
    }
    return counter;
  }

  private static class Rect {
    private int height;
    private int width;

    Rect(int height, int width) {
      this.height = height;
      this.width = width;
    }

    public int getHeight() {
      return height;
    }

    public int getWidth() {
      return width;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null || obj.getClass() != this.getClass())
        return false;
      Rect geek = (Rect) obj;
      return (geek.height == this.height) && (geek.width == width);
    }

    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + height;
      result = prime * result + width;
      return result;
    }
  }
}

Code: 18:04:20 UTC, java, verify, result: Passed

show code in pop-up

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");


class Solution {
  public int solution(int[] A, int[] B) {
    // write your code in Java SE 8
    List<Rect> list = new ArrayList<>();


    for (int i = 0; i < A.length; i++) {
      Rect opt1 = new Rect(A[i], B[i]);
      Rect opt2 = new Rect(B[i], A[i]);
      if (opt1.equals(opt2)) {
        list.add(opt1);
      } else {
        list.add(opt1);
        list.add(opt2);
      }
    }

    int heightCount = getCounter(list, "height");
    int widthCount = getCounter(list, "width");
    if (heightCount > widthCount) {
      return heightCount;
    } else if (widthCount > heightCount) {
      return widthCount;
    } 
    return heightCount;
  }

  private static int getCounter(final List<Rect> sortedList, String type) {
    Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
    int counter = 0;
    if ("height".equals(type)) {
      for (Rect rec : sortedList) {
        if (!countMap.containsKey(rec.height)) {
          countMap.put(rec.height, 1);
          if (counter == 0) {
            counter = 1;
          }
        } else {
          int tempCounter = countMap.get(rec.height) + 1;
          if (tempCounter > counter)
            counter = tempCounter;
          countMap.replace(rec.height, tempCounter);
        }
      }
    } else if ("width".equals(type)) {
      for (Rect rec : sortedList) {
        if (!countMap.containsKey(rec.width)) {
          countMap.put(rec.width, 1);
          if (counter == 0) {
            counter = 1;
          }
        } else {
          int tempCounter = countMap.get(rec.width) + 1;
          if (tempCounter > counter)
            counter = tempCounter;
          countMap.replace(rec.width, tempCounter);
        }
      }
    }
    return counter;
  }

  private static class Rect {
    private int height;
    private int width;

    Rect(int height, int width) {
      this.height = height;
      this.width = width;
    }

    public int getHeight() {
      return height;
    }

    public int getWidth() {
      return width;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null || obj.getClass() != this.getClass())
        return false;
      Rect geek = (Rect) obj;
      return (geek.height == this.height) && (geek.width == width);
    }

    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + height;
      result = prime * result + width;
      return result;
    }
  }
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.008 s

▶

example2
Second example test.

✔

0.012 s

▶

example3
Third example test.

✔

0.012 s

Code: 18:04:28 UTC, java, verify, result: Passed

show code in pop-up

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");


class Solution {
  public int solution(int[] A, int[] B) {
    // write your code in Java SE 8
    List<Rect> list = new ArrayList<>();


    for (int i = 0; i < A.length; i++) {
      Rect opt1 = new Rect(A[i], B[i]);
      Rect opt2 = new Rect(B[i], A[i]);
      if (opt1.equals(opt2)) {
        list.add(opt1);
      } else {
        list.add(opt1);
        list.add(opt2);
      }
    }

    int heightCount = getCounter(list, "height");
    int widthCount = getCounter(list, "width");
    if (heightCount > widthCount) {
      return heightCount;
    } else if (widthCount > heightCount) {
      return widthCount;
    } 
    return heightCount;
  }

  private static int getCounter(final List<Rect> sortedList, String type) {
    Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
    int counter = 0;
    if ("height".equals(type)) {
      for (Rect rec : sortedList) {
        if (!countMap.containsKey(rec.height)) {
          countMap.put(rec.height, 1);
          if (counter == 0) {
            counter = 1;
          }
        } else {
          int tempCounter = countMap.get(rec.height) + 1;
          if (tempCounter > counter)
            counter = tempCounter;
          countMap.replace(rec.height, tempCounter);
        }
      }
    } else if ("width".equals(type)) {
      for (Rect rec : sortedList) {
        if (!countMap.containsKey(rec.width)) {
          countMap.put(rec.width, 1);
          if (counter == 0) {
            counter = 1;
          }
        } else {
          int tempCounter = countMap.get(rec.width) + 1;
          if (tempCounter > counter)
            counter = tempCounter;
          countMap.replace(rec.width, tempCounter);
        }
      }
    }
    return counter;
  }

  private static class Rect {
    private int height;
    private int width;

    Rect(int height, int width) {
      this.height = height;
      this.width = width;
    }

    public int getHeight() {
      return height;
    }

    public int getWidth() {
      return width;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null || obj.getClass() != this.getClass())
        return false;
      Rect geek = (Rect) obj;
      return (geek.height == this.height) && (geek.width == width);
    }

    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + height;
      result = prime * result + width;
      return result;
    }
  }
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.004 s

▶

example2
Second example test.

✔

0.008 s

▶

example3
Third example test.

✔

0.008 s

Code: 18:04:33 UTC, java, final, score: 100

show code in pop-up

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");


class Solution {
  public int solution(int[] A, int[] B) {
    // write your code in Java SE 8
    List<Rect> list = new ArrayList<>();


    for (int i = 0; i < A.length; i++) {
      Rect opt1 = new Rect(A[i], B[i]);
      Rect opt2 = new Rect(B[i], A[i]);
      if (opt1.equals(opt2)) {
        list.add(opt1);
      } else {
        list.add(opt1);
        list.add(opt2);
      }
    }

    int heightCount = getCounter(list, "height");
    int widthCount = getCounter(list, "width");
    if (heightCount > widthCount) {
      return heightCount;
    } else if (widthCount > heightCount) {
      return widthCount;
    } 
    return heightCount;
  }

  private static int getCounter(final List<Rect> sortedList, String type) {
    Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
    int counter = 0;
    if ("height".equals(type)) {
      for (Rect rec : sortedList) {
        if (!countMap.containsKey(rec.height)) {
          countMap.put(rec.height, 1);
          if (counter == 0) {
            counter = 1;
          }
        } else {
          int tempCounter = countMap.get(rec.height) + 1;
          if (tempCounter > counter)
            counter = tempCounter;
          countMap.replace(rec.height, tempCounter);
        }
      }
    } else if ("width".equals(type)) {
      for (Rect rec : sortedList) {
        if (!countMap.containsKey(rec.width)) {
          countMap.put(rec.width, 1);
          if (counter == 0) {
            counter = 1;
          }
        } else {
          int tempCounter = countMap.get(rec.width) + 1;
          if (tempCounter > counter)
            counter = tempCounter;
          countMap.replace(rec.width, tempCounter);
        }
      }
    }
    return counter;
  }

  private static class Rect {
    private int height;
    private int width;

    Rect(int height, int width) {
      this.height = height;
      this.width = width;
    }

    public int getHeight() {
      return height;
    }

    public int getWidth() {
      return width;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null || obj.getClass() != this.getClass())
        return false;
      Rect geek = (Rect) obj;
      return (geek.height == this.height) && (geek.width == width);
    }

    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + height;
      result = prime * result + width;
      return result;
    }
  }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N)) or O(N)

expand all Example tests

▶

example1
First example test.

✔

0.012 s

▶

example2
Second example test.

✔

0.012 s

▶

example3
Third example test.

✔

0.012 s

expand all Correctness tests

▶

common_side_from_A
No rotations needed. Common side can be chosen from A. N = 15.

✔

0.012 s

▶

common_side_from_B
No rotations needed. Common side can be chosen from B. N = 15.

✔

0.012 s

▶

A_less_than_B
Array A contains shorter sides. N = 15.

✔

0.012 s

▶

A_greater_than_B
Array A contains longer sides. N = 15.

✔

0.008 s

0.012 s

▶

only_squares
All rectangles are squares. N = 15.

✔

0.012 s

▶

no_squares
Rectangles are not squares. N = 15.

✔

0.012 s

0.016 s

0.012 s

expand all Correctness/performance tests

▶

corners
N <= 2.

✔

0.012 s

0.016 s

0.012 s

0.008 s

▶

medium_common_side_from_A
No rotations needed. Common side can be chosen from A. N = 200.

✔

0.016 s

▶

medium_common_side_from_B
No rotations needed. Common side can be chosen from B. N = 200.

✔

0.016 s

0.012 s

▶

medium_A_less_than_B
"Array A contains shorter sides. N = 200.

✔

0.016 s

▶

medium_A_greater_than_B
Array A contains longer sides. N = 200.

✔

0.016 s

0.012 s

▶

medium_only_squares
All rectangles are squares. N = 200.

✔

0.012 s

expand all Performance tests

▶

large_common_side_from_A
No rotations needed. Common side can be chosen from A. N = 100,000.

✔

2.112 s

2.044 s

▶

large_common_side_from_B
No rotations needed. Common side can be chosen from B. N = 100,000.

✔

2.208 s

2.252 s

2.164 s

▶

large_A_less_than_B
Array A contains shorter sides. N = 100,000. Points x 2.

✔

1.740 s

2.104 s

2.220 s

2.116 s

▶

large_A_greater_than_B
Array A contains longer sides. N = 100,000. Points x 2.

✔

2.256 s

2.240 s

2.336 s

2.288 s

▶

large_only_squares
All rectangles are squares. N = 100,000. Points x 2.

✔

2.092 s

2.088 s