Problem

896. Monotonic Array

Java

One Pass

© Approach 3: One Pass (Simple Variant)

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean isMonotonic(int[] A) {
        boolean increasing = true;
        boolean decreasing = true;
        for (int i = 0; i < A.length - 1; i++) {
            if (A[i] > A[i + 1]) decreasing = false;
            if (A[i] < A[i + 1]) increasing = false;
        }
        return increasing || decreasing;
    }
}

Submission Detail

• 366 / 366 test cases passed.
• Runtime: 1 ms, faster than 100.00% of Java online submissions for Monotonic Array.
• Memory Usage: 47.8 MB, less than 18.59% of Java online submissions for Monotonic Array.

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public boolean isMonotonic(int[] A) {
        final int N = A.length;
        if (N<=2)
            return true;
        int[] d = new int[N-1];
        for(int i=1, j=0; i<N; i++,j++) {
            d[j] = A[i]-A[i-1];
        }
        int min=d[0],max=d[0];
        for(int i=1; i<N-1; i++) {
            if (d[i]<min) min = d[i];
            if (d[i]>max) max = d[i];
        }
        return (min<=0 && max<=0) || (min>=0 && max>=0);
    }
}

Submission Detail

• 366 / 366 test cases passed.
• Runtime: 2 ms, faster than 31.40% of Java online submissions for Monotonic Array.
• Memory Usage: 46.9 MB, less than 18.59% of Java online submissions for Monotonic Array.

Problem

1232. Check If It Is a Straight Line

similar question

• 1037. Valid Boomerang
• 149. Max Points on a Line

Java

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    private boolean isColine(int x1, int y1, int x2, int y2, int x3, int y3) {
        int a = (y3 - y2) * (x3 - x1);
        int b = (y3 - y1) * (x3 - x2);
        return a == b;
    }

    public boolean checkStraightLine(int[][] coordinates) {
        final int N = coordinates.length;
        boolean b;
        for (int i = 0; i < N - 2; i++) {
            b = isColine(coordinates[i][0], coordinates[i][1], coordinates[i + 1][0], coordinates[i + 1][1], coordinates[i + 2][0], coordinates[i + 2][1]);
            if (b == false)
                return false;
        }
        return true;
    }
}

Submission Detail

• 79 / 79 test cases passed.
• Runtime: 1 ms, faster than 22.67% of Java online submissions for Check If It Is a Straight Line.
• Memory Usage: 41 MB, less than 6.80% of Java online submissions for Check If It Is a Straight Line.

Computational geometry method

© Copyright 2002-2020, Robert Sedgewick and Kevin Wayne.

keys

• Shoelace formula, also known as Gauss’s area formula
• vertices must listed in clockwise(or counterclockwise, increasing order of polar angle) order
• CCW: Given three points a, b, and c, is a→b→c a counterclockwise turn? Determinant (or cross product) gives 2x signed area of planar triangle.

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

import java.util.Comparator;
import java.util.Arrays;

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        final int N = coordinates.length;
        Point2D[] a = new Point2D[N];
        for (int i = 0; i < N; i++) {
            a[i] = new Point2D(coordinates[i][0], coordinates[i][1]);
        }
        Arrays.sort(a);
        Arrays.sort(a, 1, N, a[0].polarOrder());
        int A = a[N - 1].x() * a[0].y() - a[0].x() * a[N - 1].y();
        for (int i = 0; i < N - 1; i++) {
            A += a[i].x() * a[i + 1].y() - a[i + 1].x() * a[i].y();
        }
        return A == 0;
    }
}

final class Point2D implements Comparable<Point2D> {
    private final int x;
    private final int y;

    public Point2D(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x() {
        return x;
    }

    public int y() {
        return y;
    }

    public static int ccw(Point2D a, Point2D b, Point2D c) {
        int area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
        if (area2 < 0) return -1;
        else if (area2 > 0) return +1;
        else return 0;
    }

    public int compareTo(Point2D that) {
        if (this.y < that.y) return -1;
        if (this.y > that.y) return +1;
        if (this.x < that.x) return -1;
        if (this.x > that.x) return +1;
        return 0;
    }

    public Comparator<Point2D> polarOrder() {
        return new PolarOrder();
    }

    private class PolarOrder implements Comparator<Point2D> {
        public int compare(Point2D q1, Point2D q2) {
            int dx1 = q1.x - x;
            int dy1 = q1.y - y;
            int dx2 = q2.x - x;
            int dy2 = q2.y - y;

            if (dy1 >= 0 && dy2 < 0) return -1;
            else if (dy2 >= 0 && dy1 < 0) return +1;
            else if (dy1 == 0 && dy2 == 0) {
                if (dx1 >= 0 && dx2 < 0) return -1;
                else if (dx2 >= 0 && dx1 < 0) return +1;
                else return 0;
            } else return -ccw(Point2D.this, q1, q2);
        }
    }
}

Submission Detail

• 79 / 79 test cases passed.
• Runtime: 6 ms, faster than 9.07% of Java online submissions for Check If It Is a Straight Line.
• Memory Usage: 38.8 MB, less than 6.80% of Java online submissions for Check If It Is a Straight Line.

Problem

832. Flipping an Image

similar question : 48. Rotate Image

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        final int N = A.length;
        final int M = A[0].length;
        int tmp;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M/2; j++) {
                tmp = A[i][j];
                A[i][j] = A[i][N-1-j];
                A[i][N-1-j] = tmp;
            }
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                A[i][j] = A[i][j]==0?1:0;
            }
        }
        return A;
    }
}

Submission Detail

• 82 / 82 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Flipping an Image.
• Memory Usage: 39.1 MB, less than 16.27% of Java online submissions for Flipping an Image.

It’s easy indeed.

Problem

905. Sort Array By Parity

Java

Two Pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int[] sortArrayByParity(int[] A) {
        final int N = A.length;
        int[] B = new int[N];
        int left=0, right=N-1;
        for(int i=0; i<N; i++) {
            if ((A[i]&1)==0) {
                B[left++]=A[i];
            }
            else {
                B[right--]=A[i];
            }
        }
        return B;
    }
}

Submission Detail

• 285 / 285 test cases passed.
• Runtime: 1 ms, faster than 99.47% of Java online submissions for Sort Array By Parity.
• Memory Usage: 40.1 MB, less than 30.13% of Java online submissions for Sort Array By Parity.

In-Place

© Solution - Approach 3: In-Place

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int[] sortArrayByParity(int[] A) {
        final int N = A.length;
        int left = 0, right = N - 1;
        int temp;
        while (left < right) {
            if ((A[left] & 1)==1 && (A[right] & 1)==0) {
                temp = A[left];
                A[left] = A[right];
                A[right] = temp;
            }
            if ((A[left] & 1) == 0) left++;
            if ((A[right] & 1) == 1) right--;
        }
        return A;
    }
}

Submission Detail

• 285 / 285 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Array By Parity.
• Memory Usage: 39.6 MB, less than 30.13% of Java online submissions for Sort Array By Parity.

Problem

1154. Day of the Year

Java

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int dayOfYear(String date) {
        int year = Integer.parseInt(date.substring(0,4));
        int month = Integer.parseInt(date.substring(5,7));
        int day = Integer.parseInt(date.substring(8,10));
        int[] dayOfMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        boolean leapYear = ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0);
        if (leapYear)
            dayOfMonth[1] = 29;
        int dy = day;
        for (int i = 1; i < month; i++) {
            dy += dayOfMonth[i - 1];
        }
        return dy;    
    }
}

Submission Detail

• 246 / 246 test cases passed.
• Runtime: 1 ms, faster than 98.63% of Java online submissions for Day of the Year.
• Memory Usage: 37.1 MB, less than 7.99% of Java online submissions for Day of the Year.

java8 LocalDate

1
2
3
4
5
6
7
8
9

import java.time.LocalDate;
import java.time.format.DateTimeFormatter;

class Solution {
    public int dayOfYear(String date) {
        LocalDate d = LocalDate.parse(date, DateTimeFormatter.ofPattern("yyyy-MM-dd"));
        return d.getDayOfYear();
    }
}

Submission Detail

• 246 / 246 test cases passed.
• Runtime: 16 ms, faster than 6.07% of Java online submissions for Day of the Year.
• Memory Usage: 38.3 MB, less than 7.64% of Java online submissions for Day of the Year.

• Leap year
• Java program to find if the given number is a leap year?

© Career advice - What’s new - By Terence Tao

Advice is what we ask for when we already know the answer but wish we didn’t. (Erica Jong)

If you can give your son or daughter only one gift, let it be enthusiasm. (Bruce Barton)

Sports serve society by providing vivid examples of excellence. (George Will)

A college degree is not a sign that one is a finished product but an indication a person is prepared for life. (Edward Malloy)

Chaque vérité que je trouvois étant une règle qui me servoit après à en trouver d’autres [Each truth that I discovered became a rule which then served to discover other truths]. (René Descartes, “Discours de la Méthode“)

When you have mastered numbers, you will in fact no longer be reading numbers, any more than you read words when reading books. You will be reading meanings. (Harold Geneen, “Managing”)

The history of every major galactic civilization tends to pass through three distinct and recognizable phases, those of Survival, Inquiry and Sophistication, otherwise known as the How, Why, and Where phases. For instance, the first phase is characterized by the question ‘How can we eat?’, the second by the question ‘Why do we eat?’ and the third by the question, ‘Where shall we have lunch?’ (Douglas Adams, “The Hitchhiker’s Guide to the Galaxy“)

行名失己, 非士也 [One who pursues fame at the risk of losing one’s self, is not a scholar]. (莊子 [Zhuangzi], “大宗師 [The Grandmaster]”)

The three pillars of learning; seeing much, suffering much, and studying much. (Welsh triad; later attributed to Benjamin Disraeli)

Better beware of notions like genius and inspiration; they are a sort of magic wand and should be used sparingly by anybody who wants to see things clearly. (José Ortega y Gasset, “Notes on the novel”)

Every mathematician worthy of the name has experienced … the state of lucid exaltation in which one thought succeeds another as if miraculously… this feeling may last for hours at a time, even for days. Once you have experienced it, you are eager to repeat it but unable to do it at will, unless perhaps by dogged work… (André Weil, “The Apprenticeship of a Mathematician”)

Integrity without knowledge is weak and useless, and knowledge without integrity is dangerous and dreadful. (Samuel Johnson, “Rasselas”)

No profit grows where is no pleasure ta’en;
In brief, sir, study what you most affect.
(William Shakespeare, “The Taming of the Shrew“)

Worse than being blind, is to see and have no vision. (Helen Keller)

Don’t just read it; fight it! Ask your own questions, look for your own examples, discover your own proofs. Is the hypothesis necessary? Is the converse true? What happens in the classical special case? What about the degenerate cases? Where does the proof use the hypothesis? (Paul Halmos, “I want to be a mathematician”)

Know how to listen, and you will profit even from those who talk badly. (Plutarch)

It is the province of knowledge to speak and it is the privilege of wisdom to listen. (Oliver Wendell Holmes, “The Poet at the Breakfast Table”)

The best teacher is the one who suggests rather than dogmatizes, and inspires his listener with the wish to teach himself. (Edward Bulwer-Lytton)

Millions long for immortality who do not know what to do with themselves on a rainy Sunday afternoon. (Susan Ertz, “Anger in the Sky”)

Every composer knows the anguish and despair occasioned by forgetting ideas which one had no time to write down. (Hector Berlioz)

We must get beyond textbooks, go out into the bypaths… and tell the world the glories of our journey. (John Hope Franklin)

Even fairly good students, when they have obtained the solution of the problem and written down neatly the argument, shut their books and look for something else. Doing so, they miss an important and instructive phase of the work. … A good teacher should understand and impress on his students the view that no problem whatever is completely exhausted.
One of the first and foremost duties of the teacher is not to give his students the impression that mathematical problems have little connection with each other, and no connection at all with anything else. We have a natural opportunity to investigate the connections of a problem when looking back at its solution. (George Pólya, “How to Solve It“)

An education isn’t how much you have committed to memory, or even how much you know. It’s being able to differentiate between what you do know and what you don’t. (Anatole France)

I suppose it is tempting, if the only tool you have is a hammer, to treat everything as if it were a nail. (Abraham Maslow, “Psychology of Science”)

A successful individual typically sets his next goal somewhat but not too much above his last achievement. In this way he steadily raises his level of aspiration. (Kurt Lewin)

It is not the strongest of the species that survives, nor the most intelligent, but the one most responsive to change. (Leon C. Megginson)

If I have ever made any valuable discoveries, it has been owing more to patient attention, than to any other talent. (Isaac Newton)

Think like a wise man, but communicate in the language of the people. (William Butler Yeats)

The mediocre teacher tells. The good teacher explains. The superior teacher demonstrates. The great teacher inspires. (William Ward)

An expert is a man who has made all the mistakes, which can be made, in a very narrow field. (Niels Bohr)

It is a mistake to suppose that men succeed through success; they much oftener succeed through failures. Precept, study, advice, and example could never have taught them so well as failure has done. (Samuel Smiles)

It is much easier to try one’s hand at many things than to concentrate one’s powers on one thing. (Quintilian)

When man is serene and healthy the pulse of the heart flows and connects, just as pearls are joined together or like a string ofred jade then one can speak ofa healthy heart. - Huang Ti (The Yellow Emperor) (2697-2597 BC)
Nei Ching Su Wen, Bk. 5, Sect. 18
(tr. by Ilza Veith in The Yellow Emperor’s Classic of Internal Medicine)

The final sessions of the International Heart Health Conference, held May 24 to 29, 1992, in Victoria, focused on the refinement of the Victoria Declaration on Heart Health. This declaration, along with two supporting documents (“Call for action” and “Framework for policy and action”), was prepared by the Advisory Board of the International Heart Health Conference.

The declaration was authorized by the individual advisory board members and not their respective organizations. Other contributors were the members of the Scientific and Program Committee of the International Heart Health Conference and individual participants at the conference. Readers are invited to use the declaration as their personal document to influence their professional associations and municipal, state, provincial or federal governments. However, no policy statement on cardiovascular disease can ever be complete, so complex is the field. We urge that you build upon the declaration and use it as a starting point for critical re-examination of its relevance to you, your institutions, your community and your country. We, in turn, will continue to pursue adoption of the declaration through advocacy and refinement of the recommendations as needed.

The following is the executive summary and the declaration.

Executive summary

Cardiovascular disease is largely preventable. We have the scientific knowledge to create a world in which heart disease and stroke are rare. In such a world everyone, from infant to elderly person, would have access to and would practise positive healthy living.

In most cases cardiovascular disease is brought about by some combination of the following factors: smoking, high blood pressure, elevated blood cholesterol level, unhealthy dietary habits(including excessive alcohol consumption), obesity, a sedentary lifestyle and psychosocial stress.

Healthy living includes good nutrition, a tobacco-free lifestyle, regular physical exercise and supportive environments. To implement a global policy of cardiovascular disease prevention, we must unite people and their communities with health care professionals,scientists, industry and policymakers.

From studying downward trends in cardiovascular disease in certain industrialized countries, we are learning how to reduce the toll of such disease, although it still remains a major problem.

The primary challenge now is to maintain the downward trend while assisting and encouraging countries where rates of heart disease are increasing(developing countries and those in central and eastern Europe) to prevent the epidemic from spreading.

The prescription is simple. To implement it is more difficult. The promotion of heart health on a global scale requires clear agreement on policy principles, implementation processes and the partnerships to make it happen.

The prevention of cardiovascular disease requires the prevention of the onset of risk factors in children and youth everywhere and in entire populations of countries where cardiovascular disease has not yet reached epidemic proportions as well as the elimination or reduction of risk factors in all populations.

The control of cardiovascular disease requires healthy living for everybody, regardless of age, sex, race or socioeconomic status. It also requires equitable access and appropriate treatment for people who are at high risk of or have cardiovascular disease.

This will require mutual assistance involving people and communities within countries and between nations; a balance between prevention and treatment and between basic, applied and evaluative research; extensive communication, education and feedback evaluation at all levels; and action by individuals, many professional associations, communities and governments.

The advisory board believes that all concerned with improving the health and quality of life of people around the world have a responsibility to heed this “call for action.” It can be done.

Declaration

Recognizing that the scientific knowledge and widely tested methods exist to prevent most cardiovascular disease, the Advisory Board of the International Heart Health Conference calls upon professionals in health care, media, education and social science, and their associations, the scientific research community, government agencies concerned with health, education, trade, commerce and agriculture, the private sector, international organizations and agencies concerned with health and economic development, community health coalitions, voluntary health organizations and employers to join forces in eliminating this modern epidemic through the adoption of policies and the implementation of programs of health promotion and disease prevention, as well as through regulatory change directed at entire populations.

Problem

1002. Find Common Characters

Java

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

class Solution {
    public List<String> commonChars(String[] A) {
        List<String> clist = new ArrayList<String>();
        final int N = A.length;
        int[][] counter = new int[26][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < A[i].length(); j++) {
                counter[A[i].charAt(j) - 'a'][i]++;
            }
        }

        int m;
        String s = "";
        for (int i = 0; i < 26; i++) {
            m = counter[i][0];
            for (int j = 1; j < N; j++) {
                if (counter[i][j] < m)
                    m = counter[i][j];
            }
            if (m > 0) {
                s = (char)(i + 'a') + "";
                for (; m > 0; m--) {
                    clist.add(s);
                }
            }
        }
        return clist;
    }
}

Submission Detail

• 83 / 83 test cases passed.
• Runtime: 7 ms, faster than 53.85% of Java online submissions for Find Common Characters.
• Memory Usage: 39.4 MB, less than 7.83% of Java online submissions for Find Common Characters.

Easy indeed! I can do it on leetcode editor without IDE debug.

Problem

1572. Matrix Diagonal Sum

Java

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int diagonalSum(int[][] mat) {
        final int N = mat.length;
        int sum = 0;
        for(int i=0;i<N;i++) {
            sum += mat[i][i];
            if ((N-1)!=2*i)
                sum += mat[i][N-1-i];
        }
        return sum;
    }
}

Submission Detail

• 113 / 113 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Matrix Diagonal Sum.
• Memory Usage: 39.5 MB, less than 16.30% of Java online submissions for Matrix Diagonal Sum.

by John Lennon

Verse 1

Imagine there’s no heaven
It’s easy if you try
No hell below us
Above us, only sky
Imagine all the people
Living for today
I

Verse 2

Imagine there’s no countries
It isn’t hard to do
Nothing to kill or die for
And no religion too
Imagine all the people
Living life in peace
You

Chorus

You may say I’m a dreamer
But I’m not the only one
I hope someday you’ll join us
And the world will be as one

Verse 3

Imagine no possessions
I wonder if you can
No need for greed or hunger
A brotherhood of man
Imagine all the people
Sharing all the world
You

Chorus

You may say I’m a dreamer
But I’m not the only one
I hope someday you’ll join us
And the world will live as one

• Imagine - John Lennon song
• Imagine