Start learning free

LESSON 560 OF 569 · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

Shapes Perimeter in Java: Polymorphism with a Common Type

Practice O(n) Read the full explanation

A drawing app keeps rectangles, squares and triangles in one list. Write the shape types so that code holding that list can ask any shape for its name and its perimeter (the length all the way around it) without knowing which kind of shape it is. That is polymorphism: one call, shape.perimeter(), and each kind of shape runs its own version.

Every shape class inherits from the class Shape, the common type. Shape has two methods:

  • name() returns the kind of shape as text: "Shape" for a plain Shape.
  • perimeter() returns the length around the shape: 0 for a plain Shape.

Each shape class overrides both:

  • Rectangle(width, height): its name is "Rectangle", its perimeter 2 × (width + height).
  • Square(side): its name is "Square", its perimeter 4 × side.
  • Triangle(a, b, c): its name is "Triangle", its perimeter a + b + c.

In Java each shape class extends Shape and marks its versions of the methods with @Override. Each class keeps its sizes in public int fields.

Then write two methods of the class Solution, as in the course's other lessons. Both get the shapes as Shape[]:

  • totalPerimeter(shapes) returns the sum of the perimeters of all the shapes.
  • largestShape(shapes) returns the name of the shape with the largest perimeter. If several shapes share the largest perimeter, the one that comes first wins.

Both functions must work through the common type's methods only: never check which kind a shape is. Then a new kind of shape, added later, works with them unchanged.

The starter code already has every class, constructor and method header: write their bodies. For each test, the harness reads the shapes, builds them in the order given, calls totalPerimeter and largestShape, and prints the two results on one line, separated by a space.

 

Example 1:

Input:
    new Rectangle(3, 4)
    new Square(5)
    new Triangle(3, 4, 5)
Output: 46 Square
Explanation: The perimeters are 2 × (3 + 4) = 14, 4 × 5 = 20 and 3 + 4 + 5 = 12. Their total is 46, and the square's 20 is the largest.

Example 2:

Input:
    new Rectangle(2, 4)
    new Square(3)
    new Triangle(4, 4, 4)
Output: 36 Rectangle
Explanation: All three perimeters are 12: 2 × (2 + 4), 4 × 3 and 4 + 4 + 4. On a tie the shape that comes first in the list wins, so the answer is the rectangle.

Example 3:

Input:
    new Square(1)
    new Rectangle(1, 1)
    new Triangle(2, 2, 3)
Output: 15 Triangle
Explanation: The perimeters are 4, 4 and 7, so the last shape, the triangle, is the largest. A 1 by 1 rectangle has the same sides as a square, but it is still a Rectangle: each object answers name() for its own class.

 

Constraints:

  • Every test has between 1 and 100 shapes: the list is never empty.
  • Every size (width, height, side, and each side of a triangle) is an integer from 1 to 104.
  • A triangle's three sides always make a real triangle: each side is shorter than the other two together.

Note:

Each function looks at every shape once: O(n) time for n shapes, and no extra space.

STEP 1 OF 24
    Ctrl + Enter to check

    JAVA · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

    Shapes Perimeter in Java, explained

    Problem overview

    A drawing app keeps rectangles, squares and triangles together. You write one class per kind of shape, all extending a common class Shape, plus two methods in Solution that work on a Shape[]:

    • totalPerimeter(shapes) returns the sum of all the perimeters.
    • largestShape(shapes) returns the name() of the shape with the largest perimeter. On a tie, the first one in the array wins.

    The perimeters are 2 * (width + height) for Rectangle, 4 * side for Square and a + b + c for Triangle. A plain Shape is named "Shape" and has perimeter 0.

    For a Rectangle(3, 4), a Square(5) and a Triangle(3, 4, 5), the perimeters are 14, 20 and 12. The total is 46 and the largest is the square, so the result is 46 Square.

    Approach: ask the object, never check its class

    The two methods in Solution must not test what kind of shape they hold. They only call perimeter() and name(), the two methods that Shape declares. Java runs the version that belongs to the object's real class, so a Square object computes 4 * side even when the code only knows it has a Shape. This is polymorphism: one call, many behaviours.

    The payoff is that a shape added later, say a Circle with its own perimeter(), works with totalPerimeter and largestShape without touching them.

    Both methods make one pass over the array, with a running total in the first one and a running best in the second.

    Step by step

    1. Give Shape its default methods. name() returns "Shape" and perimeter() returns 0. The subclasses override both, but the common type needs them so that callers can use them.
    2. Add the fields. Rectangle keeps width and height, Square keeps side and Triangle keeps a, b and c, all as public int fields. perimeter() needs them later, so each object has to remember its sizes.
    3. Fill the constructors. The parameters have the same names as the fields, so this.width = width; stores the parameter in the field.
    4. Override name() and perimeter() in each class. Mark both with @Override so the compiler checks that the parent has them.
    5. Write totalPerimeter. Start an int total at 0, loop over the shapes with a for-each loop and add shape.perimeter().
    6. Write largestShape. Start with largest = shapes[0] (the array is never empty), loop over all the shapes, and replace largest when a shape's perimeter is strictly greater. Return largest.name().

    The solution in Java

    class Shape {
    public String name() {
        return "Shape";
    }

    public int perimeter() {
        return 0;
    }
}

class Rectangle extends Shape {
    public int width;
    public int height;

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

    @Override
    public String name() {
        return "Rectangle";
    }

    @Override
    public int perimeter() {
        return 2 * (width + height);
    }
}

class Square extends Shape {
    public int side;

    public Square(int side) {
        this.side = side;
    }

    @Override
    public String name() {
        return "Square";
    }

    @Override
    public int perimeter() {
        return 4 * side;
    }
}

class Triangle extends Shape {
    public int a;
    public int b;
    public int c;

    public Triangle(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override
    public String name() {
        return "Triangle";
    }

    @Override
    public int perimeter() {
        return a + b + c;
    }
}

class Solution {
    public int totalPerimeter(Shape[] shapes) {
        int total = 0;
        for (Shape shape : shapes) {
            total += shape.perimeter();
        }
        return total;
    }

    public String largestShape(Shape[] shapes) {
        Shape largest = shapes[0];
        for (Shape shape : shapes) {
            if (shape.perimeter() > largest.perimeter()) {
                largest = shape;
            }
        }
        return largest.name();
    }
}

    Details worth knowing

    • Strictly greater keeps the first on a tie. With >, a later shape with an equal perimeter never replaces the current one. With >= the last tied shape would win.
    • The loop can start at the first shape. Comparing shapes[0] with itself changes nothing, so a for-each over the whole array is fine.
    • The name belongs to the object. A Rectangle(1, 1) has the same sides as a Square(1), and both have perimeter 4, but the first reports "Rectangle" and the second "Square".
    • The constructors set the fields directly. The subclass constructors don't call super(...) explicitly: Shape has no constructor of its own, so Java calls its default one for you.

    Adding a new kind of shape

    To see why the rule matters, add a class the lesson doesn't have. This Pentagon extends Shape and overrides the same two methods:

    class Pentagon extends Shape {
    public int side;

    public Pentagon(int side) {
        this.side = side;
    }

    @Override
    public String name() {
        return "Pentagon";
    }

    @Override
    public int perimeter() {
        return 5 * side;
    }
}

    With the array { new Square(2), new Pentagon(3) }, the perimeters are 8 and 15. Calling totalPerimeter and largestShape on it gives 23 Pentagon, and neither method needed a single change.

    The defaults in Shape ("Shape" and 0) are never used with these three subclasses, because each one overrides both methods. They exist so the common type has the two methods that callers rely on. A plain new Shape() is allowed here and reports Shape with perimeter 0.

    Complexity

    Each method looks at every shape once and calls methods that take constant time, so both run in O(n) time for n shapes. They keep only a couple of variables, so the extra space is O(1).

    The largest possible values are small: a perimeter is at most about 4 * 10000 for one shape, and with 100 shapes the total stays far below the int limit.

    Testing

    Running the solution on three small lists gives:

    ShapesResult
    Rectangle(3, 4), Square(5), Triangle(3, 4, 5)46 Square
    Rectangle(2, 4), Square(3), Triangle(4, 4, 4)36 Rectangle
    Square(1), Rectangle(1, 1), Triangle(2, 2, 3)15 Triangle
    Square(7)28 Square

    In the second row all three perimeters are 12, so the first shape, the rectangle, wins.

    Common mistakes

    • Checking the class. Code like if (shape instanceof Square) inside totalPerimeter works for today's shapes but breaks the moment a new kind appears. Call perimeter() and let the object decide.
    • Forgetting this. in a constructor. Writing width = width; assigns the parameter to itself and leaves the field at 0.
    • Returning the perimeter instead of the name. largestShape returns a String, the result of largest.name(), not the number.
    • Forgetting the multiplication by 2 in the rectangle. width + height is only half of the way around.
    • Using >= in the comparison. That returns the last shape among equal ones, and the second example would print Triangle instead of Rectangle.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free