LeetCode - Algorithms - 389. Find the Difference

Problem

389. Find the Difference

Java

bit manipulation

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public char findTheDifference(String s, String t) {
char c = ' ';
s += t;
int x = (int) (s.charAt(0));
for (int i = 1; i < s.length(); i++) {
x ^= (int) (s.charAt(i));
}
c = (char) x;
return c;
}
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 2 ms, faster than 49.97% of Java online submissions for Find the Difference.
  • Memory Usage: 37.4 MB, less than 50.18% of Java online submissions for Find the Difference.

bucket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public char findTheDifference(String s, String t) {
char c = ' ';
final int N = 26;
int[] a = new int[N];
for (int i = 0; i < t.length(); i++) {
a[t.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
a[s.charAt(i) - 'a']--;
}
for (int i = 0; i < N; i++) {
if (a[i] > 0) {
c = (char) (i + 'a');
break;
}
}
return c;
}
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 2 ms, faster than 49.97% of Java online submissions for Find the Difference.
  • Memory Usage: 37.2 MB, less than 88.24% of Java online submissions for Find the Difference.

HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public char findTheDifference(String s, String t) {
char r = ' ';
Map<Character, Integer> map = new HashMap<Character, Integer>();
char c = ' ';
for(int i=0;i<t.length();i++) {
c = t.charAt(i);
if (map.containsKey(c))
map.put(c, map.get(c)+1);
else
map.put(c,1);
}
for(int i=0;i<s.length();i++) {
c = s.charAt(i);
if (map.containsKey(c))
map.put(c, map.get(c)-1);
}
for(Map.Entry<Character, Integer> e : map.entrySet()) {
if (e.getValue()>0)
r = e.getKey();
}
return r;
}
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 8 ms, faster than 16.46% of Java online submissions for Find the Difference.
  • Memory Usage: 37.5 MB, less than 35.41% of Java online submissions for Find the Difference.

LeetCode - Algorithms - 504. Base 7

Problem

504. Base 7

Java

jdk

public static String Integer.toString(int i, int radix)

1
2
3
4
5
class Solution {
public String convertToBase7(int num) {
return Integer.toString(num, 7);
}
}

Submission Detail

  • 241 / 241 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Base 7.
  • Memory Usage: 35.9 MB, less than 95.07% of Java online submissions for Base 7.

Why every student should study computer science

by Robert Sedgewick

Every college student needs a computer science course, and most need two or more. More and more educators are beginning to recognize this truth, but we are a long way from meeting the need.

Should we require all college students to take a computer science course? That is perhaps debatable. But, without question, we need to make such courses available to all students.

Colleges and universities offer the opportunity for any student to take as many courses as they desire in math, history, English, psychology and almost any other discipline, taught by faculty members in that discipline. Students should have the same opportunity with computer science. But at far too many institutions today – including many of the
most prestigious in the country – students who are not computer science majors encounter severe enrollment caps, watered-down computer science for nonmajors courses or courses that just teach programming skills. They deserve better.

Many students need computer science to prepare for success later on in the curriculum. Archaeologists write programs to piece together fragments of ancient ruins. Economists apply deep learning models to financial data. Linguists write programs to study statistical properties of literary works. Physicists study computational models of the universe to analyze its origins. Musicians work with synthesized sound. Biologists seek patterns in genomes. Geologists study the evolution of landscapes. Artists work with digital images. The list goes on and on.

Programming is an intellectually satisfying experience, and certainly useful, but computer science is about much more than just programming. The understanding of what we can and cannot do with computation is arguably the most important intellectual achievement of the past century, and it has led directly to the development of the computational infrastructure that surrounds us. The theory and the practice are interrelated in fascinating ways. Whether one thinks that the purpose of a college education is to prepare students for the workplace or to develop foundational knowledge with lifetime benefits (or both), computer science, in the 21st century, is fundamental.

Even students who will not need to program at all are likely to have important encounters with computational thinking later in life. For example, philosophers, politicians, reporters and, well, everyone – not just software engineers – must address privacy, security and ethical issues in software.

Computer science is also fertile ground for critical thinking. How might a given program or system be improved? Why might one programming language or system be more effective than another for a given application? Is a given approach a feasible way to attempt solving a given problem? Is it even possible to solve a given problem? A course
or two in computer science can prepare any student to grapple effectively with such questions.

Steve Jobs once said on National Public Radio that “computer science is a liberal art.” Whether one believes that or not, the question is undeniably debatable and in the best tradition of the liberal arts! And one cannot begin to address the question without familiarity with the basics. Computer science is grounded in logic and mathematics and relevant to philosophy, the natural sciences and other liberal arts, so it belongs in the education of any liberal arts student. Just to pick one example, developments over the past century in computer science have taken logic, one of the bedrocks of the ancient liberal arts, to new levels. Computer science is not just useful. It expands the mind.

Courses for Every Student

Whatever major they might eventually choose, students nowadays know that computer science is pervasive and that they need to learn as much as they can about it. But unfortunately, opportunities to do so are limited for far too many students. Before seriously considering the idea of requirements, colleges and universities must focus on how to provide access to courses for all their students.

We are far from a national consensus, but an approach that has proven successful and has promise for the future is to invest in an introductory computer science sequence that teaches the important concepts and ideas in the field, as we do for economics, physics, mathematics, psychology, biology, chemistry and many other disciplines. For example, at my institution, Princeton University, we started work on this approach in the 1980s and now are reaching over two-thirds of all the students at the university. Other institutions have seen similar results.

When starting out at Princeton, I thought about lobbying for a computer science requirement and asked one of my senior colleagues in the physics department how we might encourage students to take a course. His response was this: “If you do a good course, they will come.” This wisdom applies in spades today. A well-designed computer science course can attract the vast majority of students at any college or university
nowadays – in fact, there’s no need for a requirement.

An important reason to develop a single introductory course that everyone takes is that it makes later courses accessible to everyone, too. Students in genomics, linguistics, astrophysics, philosophy, geosciences or whatever field who need deeper background in computer science can easily get it – as well as easily transition to computer science as a major or minor.

Perhaps the most important benefit of the approach is that it supports diversity. The typical approach of offering an accelerated curriculum to Steve Jobs wannabes and computer science for nonmajors courses to everyone else is inherently antidiversity. It sends the message to the nonmajors that they are inferior and puts them in a position where they have little chance to catch up – when, actually, they are not so far behind.

Does this put computer science majors at a disadvantage? No. They can learn their major in depth later, as do the doctors, chemical engineers, writers, historians and everyone else. Meanwhile, they can benefit from learning something about the big picture, along with everyone else.

By putting everyone in the same course, focusing on what is important, teaching programming in the context of interesting and diverse applications across many disciplines, avoiding esoteric language details that can easily be saved for later, and mixing in historical context, theory, simple abstract machines and other material that is
new to everyone, we can get all students on more or less the same playing field in one or two courses – pretty much in the same way as we do in other disciplines.

As recently noted in Inside Higher Ed, there is a supply and demand shortage “on steroids” [1] for computer science faculty, with no clear solution in sight. How can a dwindling number of faculty members possibly increase the enrollments in their courses by a factor of five or 10, in addition to everything else they must do?

Of necessity, faculty members who teaching huge computer science courses around the world have had to find ways to get the job done that are more effective and efficient than traditional methods. In recent years, it has been exciting to see scalable approaches to teaching computing on all fronts. We can replace inefficient and ineffective large live lectures with curated online videos, use modern tools to create new and better textbooks and associated online content, and develop web services to streamline assessments. Like textbooks, these materials can be shared among educational institutions, further leveraging their effectiveness. Curated videos and web services developed at one institution can be used to improve the educational
experience for students at another, in the same way as textbooks. Such developments have enabled computer science professors to reach huge numbers of students more efficiently and effectively than ever before.

Should computer science be required of all students? Maybe. But the first step for any college or university is to commit to providing access to at least a full year of computer science for each and every student. That is what their students want and need. Modern technology can help give it to them.


Robert Sedgewick is the William O. Baker ’39 Professor of Computer Science at Princeton University. He is the recipient of the Karl V. Karlstrom Outstanding Educator Award from the Association for Computing Machinery for textbooks and online materials that have educated generations of computer science students worldwide.

My English Words List - May - 2021

synonym

synonym

“Small” and “little” are synonyms.

Synonym

swab

A cotton swab

swab

Use a cotton swab dipped in alcohol to disinfect the area.

Cotton swab

pinwheel

A pinwheel

pinwheel

Pinwheel (toy)

vanilla

Vanilla planifolia, flower

Vanilla

vanilla

The frosting is flavored with vanilla.

tattoo

An example of a tattoo design

Tattoo

tattoo

furnace

Forced-air gas furnace

Furnace

furnace

isosceles

isosceles

Isosceles triangle
Isosceles triangle

isosceles trapezoid
Isosceles trapezoid

atlas

An atlas is a collection of maps.

Atlas

atlas

trophy

Trophy

Trophy

trophy

grit

grit

He shook out his shoes to remove the small rocks and grit.

Gritstone

steward

steward

teaching our children to be good stewards of the land

lily

Lilium candidum

Lilium

lily

water lily

daisy

Twelve species of Asteraceae from the subfamilies Asteroideae, Carduoideae and Cichorioideae

Asteraceae

daisy

clover

Trifolium repens, white clover

Clover

clover

robin

European robin

European robin

robin

gem

A selection of gemstone pebbles made by tumbling rough rock with abrasive grit, in a rotating drum.

Gemstone

gem

germ

bacteria

Pathogen

germ

pomegranate

Fruit of Punica granatum split open to reveal clusters of seeds on the inside sarcotesta, and a glass of juice

Pomegranate

pomegranate

chickadee

Black-capped chickadee

chickadee

Chickadee

thrush

Groundscraper thrush

thrush

Thrush (bird)

patty

A ground beef hamburger patty

patty

a hamburger patty

Patty

blazer

A single-breasted, reefer-style, navy blue blazer, dressed with brass buttons.

blazer

He wore a blue blazer and khaki pants.

Blazer

pavilion

Pavilion at the Nanhai Academy in Taipei, Taiwan

pavilion

Pavilion

marmalade

Homemade marmalade

marmalade

Marmalade

lasagna

Baked meat lasagne

lasagna

Lasagne

rugby

Rugby union: A scrum between the Crusaders and the Brumbies

rugby

Rugby football

porridge

A bowl of oatmeal porridge

porridge

Porridge

cannon

Cannon from the 15th century at Šibenik city walls

cannon

Cannon

canoe

A B.N. Morris Canoe Company wood-and-canvas canoe built approximately 1912

canoe

Canoe

referee

A referee issues a yellow card to a player during a game of association football.

referee

Referee

llama

A domestic llama

llama

Llama

LeetCode - Algorithms - 946. Validate Stack Sequences

Problem

946. Validate Stack Sequences

Analysis

Forbidden triple for stack generability

© https://algs4.cs.princeton.edu/13stacks/

a permutation can be generated by a stack if and only if it has no forbidden triple (a, b, c) such that a < b < c with c first, a second, and b third (possibly with other intervening integers between c and a and between a and b).

Java

Greedy

© Validate Stack Sequences

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new LinkedList<Integer>();
int j = 0;
for (int i = 0; i < pushed.length; i++) {
stack.addFirst(pushed[i]);
while (!stack.isEmpty() && stack.peekFirst() == popped[j]) {
stack.removeFirst();
j++;
}
}
if (stack.isEmpty())
return true;
else
return false;
}
}

Submission Detail

  • 152 / 152 test cases passed.
  • Runtime: 1 ms, faster than 93.97% of Java online submissions for Validate Stack Sequences.
  • Memory Usage: 38.4 MB, less than 90.26% of Java online submissions for Validate Stack Sequences.

no stack

© no stack solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int i = 0;
for (int k = 0, j = 0; k < pushed.length; k++) {
pushed[i] = pushed[k];
while (i >= 0 && pushed[i] == popped[j]) {
i--;
j++;
}
i++;
}
return i == 0;
}
}

Submission Detail

  • 152 / 152 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Stack Sequences.
  • Memory Usage: 38.9 MB, less than 18.73% of Java online submissions for Validate Stack Sequences.

A Universe of Atoms, An Atom In The Universe

by Richard Feynman

I stand at the seashore, alone, and start to think.
There are the rushing waves
mountains of molecules
each stupidly minding its own business
trillions apart
yet forming white surf in unison.

Ages on ages,
before any eyes could see
year after year,
thunderously pounding the shore as now.
For whom? For what?
On a dead planet
with no life to entertain.

Never at rest
tortured by energy
wasted prodigiously by the sun
poured into space.
A mite makes the sea roar.

Deep in the sea
all molecules repeat
the patterns of one another
till complex new ones are formed.
They make others like themselves
and a new dance starts.

Growing in size and complexity
living things
masses of atoms
DNA, protein
dancing a pattern ever more intricate.

Out of the cradle
onto dry land
here it is
standing:
atoms with consciousness;
matter with curiosity.

Stands at the sea,
wonders at wondering: I
a universe of atoms
an atom in the universe.


What's so sexy about math? - Cédric Villani - TED2016

What is it that French people do better than all the others? If you would take polls, the top three answers might be: love, wine and whining.

(Laughter)

Maybe. But let me suggest a fourth one: mathematics. Did you know that Paris has more mathematicians than any other city in the world? And more streets with mathematicians’ names, too. And if you look at the statistics of the Fields Medal, often called the Nobel Prize for mathematics, and always awarded to mathematicians below the age of 40, you will find that France has more Fields medalists per inhabitant than any other country.

What is it that we find so sexy in math? After all, it seems to be dull and abstract, just numbers and computations and rules to apply. Mathematics may be abstract, but it’s not dull and it’s not about computing. It is about reasoning and proving our core activity. It is about imagination, the talent which we most praise. It is about finding the truth. There’s nothing like the feeling which invades you when after months of hard thinking, you finally understand the right reasoning to solve your problem. The great mathematician André Weil likened this – no kidding – to sexual pleasure. But noted that this feeling can last for hours, or even days.

The reward may be big. Hidden mathematical truths permeate our whole physical world. They are inaccessible to our senses but can be seen through mathematical lenses. Close your eyes for moment and think of what is occurring right now around you. Invisible particles from the air around are bumping on you by the billions and billions at each second, all in complete chaos. And still, their statistics can be accurately predicted by mathematical physics. And open your eyes now to the statistics of the velocities of these particles.

The famous bell-shaped Gauss Curve, or the Law of Errors – of deviations with respect to the mean behavior. This curve tells about the statistics of velocities of particles in the same way as a demographic curve would tell about the statistics of ages of individuals. It’s one of the most important curves ever. It keeps on occurring again and again, from many theories and many experiments, as a great example of the universality which is so dear to us mathematicians.

Of this curve, the famous scientist Francis Galton said, “It would have been deified by the Greeks if they had known it. It is the supreme law of unreason.” And there’s no better way to materialize that supreme goddess than Galton’s Board. Inside this board are narrow tunnels through which tiny balls will fall down randomly, going right or left, or left, etc. All in complete randomness and chaos. Let’s see what happens when we look at all these random trajectories together.

(Board shaking)

This is a bit of a sport, because we need to resolve some traffic jams in there. Aha. We think that randomness is going to play me a trick on stage.

There it is. Our supreme goddess of unreason. the Gauss Curve, trapped here inside this transparent box as Dream in “The Sandman” comics. For you I have shown it, but to my students I explain why it could not be any other curve. And this is touching the mystery of that goddess, replacing a beautiful coincidence by a beautiful explanation.

All of science is like this. And beautiful mathematical explanations are not only for our pleasure. They also change our vision of the world. For instance, Einstein, Perrin, Smoluchowski, they used the mathematical analysis of random trajectories and the Gauss Curve to explain and prove that our world is made of atoms.

It was not the first time that mathematics was revolutionizing our view of the world. More than 2,000 years ago, at the time of the ancient Greeks, it already occurred. In those days, only a small fraction of the world had been explored, and the Earth might have seemed infinite. But clever Eratosthenes, using mathematics, was able to measure the Earth with an amazing accuracy of two percent.

Here’s another example. In 1673, Jean Richer noticed that a pendulum swings slightly slower in Cayenne than in Paris. From this observation alone, and clever mathematics, Newton rightly deduced that the Earth is a wee bit flattened at the poles, like 0.3 percent – so tiny that you wouldn’t even notice it on the real view of the Earth.

These stories show that mathematics is able to make us go out of our intuition measure the Earth which seems infinite, see atoms which are invisible or detect an imperceptible variation of shape. And if there is just one thing that you should take home from this talk, it is this: mathematics allows us to go beyond the intuition and explore territories which do not fit within our grasp.

Here’s a modern example you will all relate to: searching the Internet. The World Wide Web, more than one billion web pages – do you want to go through them all? Computing power helps, but it would be useless without the mathematical modeling to find the information hidden in the data.

Let’s work out a baby problem. Imagine that you’re a detective working on a crime case, and there are many people who have their version of the facts. Who do you want to interview first? Sensible answer: prime witnesses. You see, suppose that there is person number seven, tells you a story, but when you ask where he got if from, he points to person number three as a source. And maybe person number three, in turn, points at person number one as the primary source. Now number one is a prime witness, so I definitely want to interview him – priority. And from the graph we also see that person number four is a prime witness. And maybe I even want to interview him first, because there are more people who refer to him.

OK, that was easy, but now what about if you have a big bunch of people who will testify? And this graph, I may think of it as all people who testify in a complicated crime case, but it may just as well be web pages pointing to each other, referring to each other for contents. Which ones are the most authoritative? Not so clear.

Enter PageRank, one of the early cornerstones of Google. This algorithm uses the laws of mathematical randomness to determine automatically the most relevant web pages, in the same way as we used randomness in the Galton Board experiment. So let’s send into this graph a bunch of tiny, digital marbles and let them go randomly through the graph. Each time they arrive at some site, they will go out through some link chosen at random to the next one. And again, and again, and again. And with small, growing piles, we’ll keep the record of how many times each site has been visited by these digital marbles.

Here we go. Randomness, randomness. And from time to time, also let’s make jumps completely randomly to increase the fun.

And look at this: from the chaos will emerge the solution. The highest piles correspond to those sites which somehow are better connected than the others, more pointed at than the others. And here we see clearly which are the web pages we want to first try. Once again, the solution emerges from the randomness. Of course, since that time, Google has come up with much more sophisticated algorithms, but already this was beautiful.

And still, just one problem in a million. With the advent of digital area, more and more problems lend themselves to mathematical analysis, making the job of mathematician a more and more useful one, to the extent that a few years ago, it was ranked number one among hundreds of jobs in a study about the best and worst jobs published by the Wall Street Journal in 2009.

Mathematician – best job in the world. That’s because of the applications: communication theory, information theory, game theory, compressed sensing, machine learning, graph analysis, harmonic analysis. And why not stochastic processes, linear programming, or fluid simulation? Each of these fields have monster industrial applications. And through them, there is big money in mathematics. And let me concede that when it comes to making money from the math, the Americans are by a long shot the world champions, with clever, emblematic billionaires and amazing, giant companies, all resting, ultimately, on good algorithm.

Now with all this beauty, usefulness and wealth, mathematics does look more sexy. But don’t you think that the life a mathematical researcher is an easy one. It is filled with perplexity, frustration, a desperate fight for understanding.

Let me evoke for you one of the most striking days in my mathematician’s life. Or should I say, one of the most striking nights. At that time, I was staying at the Institute for Advanced Studies in Princeton – for many years, the home of Albert Einstein and arguably the most holy place for mathematical research in the world. And that night I was working and working on an elusive proof, which was incomplete. It was all about understanding the paradoxical stability property of plasmas, which are a crowd of electrons. In the perfect world of plasma, there are no collisions and no friction to provide the stability like we are used to. But still, if you slightly perturb a plasma equilibrium, you will find that the resulting electric field spontaneously vanishes, or damps out, as if by some mysterious friction force.

This paradoxical effect, called the Landau damping, is one of the most important in plasma physics, and it was discovered through mathematical ideas. But still, a full mathematical understanding of this phenomenon was missing. And together with my former student and main collaborator Clément Mouhot, in Paris at the time, we had been working for months and months on such a proof. Actually, I had already announced by mistake that we could solve it. But the truth is, the proof was just not working. In spite of more than 100 pages of complicated, mathematical arguments, and a bunch discoveries, and huge calculation, it was not working. And that night in Princeton, a certain gap in the chain of arguments was driving me crazy. I was putting in there all my energy and experience and tricks, and still nothing was working. 1 a.m., 2 a.m., 3 a.m., not working. Around 4 a.m., I go to bed in low spirits. Then a few hours later, waking up and go, “Ah, it’s time to get the kids to school –” What is this? There was this voice in my head, I swear. “Take the second term to the other side, Fourier transform and invert in L2.”

(Laughter)

Damn it, that was the start of the solution!

You see, I thought I had taken some rest, but really my brain had continued to work on it. In those moments, you don’t think of your career or your colleagues, it’s just a complete battle between the problem and you.

That being said, it does not harm when you do get a promotion in reward for your hard work. And after we completed our huge analysis of the Landau damping, I was lucky enough to get the most coveted Fields Medal from the hands of the President of India, in Hyderabad on 19 August, 2010 – an honor that mathematicians never dare to dream, a day that I will remember until I live.

What do you think, on such an occasion? Pride, yes? And gratitude to the many collaborators who made this possible. And because it was a collective adventure, you need to share it, not just with your collaborators. I believe that everybody can appreciate the thrill of mathematical research, and share the passionate stories of humans and ideas behind it. And I’ve been working with my staff at Institut Henri Poincaré, together with partners and artists of mathematical communication worldwide, so that we can found our own, very special museum of mathematics there.

So in a few years, when you come to Paris, after tasting the great, crispy baguette and macaroon, please come and visit us at Institut Henri Poincaré, and share the mathematical dream with us.

Thank you.

(Applause)


当然,我不会考虑在一个面包质量不佳的国度彻底定居下来……澳大利亚华裔神童陶哲轩不再是我的竞争对手:他已在上届国际数学家大会上获奖,当时年仅31岁。…到2014年,我已经超龄3个月了。要想拿到“FM”,要么在2010年,要么将永远失去机会。(塞德里克·维拉尼,一个定理的诞生-我与菲尔茨奖的一千个日夜)

Can that really be Cedric Villani open-necked and without his araignée? Timothy Gowers @wtgowers

LeetCode - Algorithms - 537. Complex Number Multiplication

Problem

537. Complex Number Multiplication

Java

Complex.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
31
32
class Solution {
public String complexNumberMultiply(String a, String b) {
int re1 = Integer.parseInt(a.substring(0, a.indexOf("+")));
int im1 = Integer.parseInt(a.substring(a.indexOf("+") + 1, a.length() - 1));
Complex c1 = new Complex(re1, im1);
int re2 = Integer.parseInt(b.substring(0, b.indexOf("+")));
int im2 = Integer.parseInt(b.substring(b.indexOf("+") + 1, b.length() - 1));
Complex c2 = new Complex(re2, im2);
Complex c = c1.times(c2);
return c.toString();
}
}

class Complex {
private int re;
private int im;

public Complex(int real, int imag) {
this.re = real;
this.im = imag;
}

public String toString() {
return re + "+" + im + "i";
}

public Complex times(Complex that) {
int real = this.re * that.re - this.im * that.im;
int imag = this.re * that.im + this.im * that.re;
return new Complex(real, imag);
}
}

Submission Detail

  • 55 / 55 test cases passed.
  • Runtime: 4 ms, faster than 81.21% of Java online submissions for Complex Number Multiplication.
  • Memory Usage: 37.6 MB, less than 17.58% of Java online submissions for Complex Number Multiplication.

LeetCode - Algorithms - 334. Increasing Triplet Subsequence

Problem

334. Increasing Triplet Subsequence

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

Java

Increasing triplet subsequence problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < first)
first = nums[i];
if (nums[i] > first && nums[i] < second) {
second = nums[i];
}
if (nums[i] > second)
return true;
}
return false;
}
}

Submission Detail

  • 75 / 75 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Increasing Triplet Subsequence.
  • Memory Usage: 39.1 MB, less than 9.26% of Java online submissions for Increasing Triplet Subsequence.

Sonnet 3

by William Shakespeare

Look in thy glass and tell the face thou viewest,
Now is the time that face should form another,
Whose fresh repair if now thou not renewest,
Thou dost beguile the world, unbless some mother.
For where is she so fair whose uneared womb
Disdains the tillage of thy husbandry?
Or who is he so fond will be the tomb
Of his self-love, to stop posterity?
Thou art thy mother’s glass, and she in thee
Calls back the lovely April of her prime;
So thou through windows of thine age shalt see,
Despite of wrinkles, this thy golden time.
But if thou live rememb’red not to be,
Die single, and thine image dies with thee.