Problem

442. Find All Duplicates in an Array

Java

1

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

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        final int N = nums.length;
        int[] arr = new int[N + 1];
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]]++;
        }
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > 1) {
                list.add(i);
            }
        }
        return list;        
    }
}

Submission Detail

• 28 / 28 test cases passed.
• Runtime: 6 ms, faster than 50.21% of Java online submissions for Find All Duplicates in an Array.
• Memory Usage: 64.1 MB, less than 5.07% of Java online submissions for Find All Duplicates in an Array.

Problem

448. Find All Numbers Disappeared in an Array

Java

1

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

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        final int N = nums.length;
        int[] arr = new int[N+1];
        for(int i=0;i<nums.length;i++) {
            arr[nums[i]]++;
        }
        List<Integer> list = new ArrayList<Integer>();
        for(int i=1;i<arr.length;i++) {
            if (arr[i]==0) {
                list.add(i);
            }
        }
        return list;
    }
}

Submission Detail

• 33 / 33 test cases passed.
• Runtime: 6 ms, faster than 37.69% of Java online submissions for Find All Numbers Disappeared in an Array.
• Memory Usage: 64 MB, less than 5.08% of Java online submissions for Find All Numbers Disappeared in an Array.

Problem

1662. Check If Two String Arrays are Equivalent

Java

jdk

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        StringBuilder sb1 = new StringBuilder();
        for(int i=0;i<word1.length;i++)
            sb1.append(word1[i]);
        StringBuilder sb2 = new StringBuilder();
        for(int i=0;i<word2.length;i++)
            sb2.append(word2[i]);
        return sb1.toString().equals(sb2.toString());
    }
}

Submission Detail

• 109 / 109 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Check If Two String Arrays are Equivalent.
• Memory Usage: 36.7 MB, less than 88.84% of Java online submissions for Check If Two String Arrays are Equivalent.

Problem

700. Search in a Binary Search Tree

Java

Recursion

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode recur(TreeNode node, int val) {
        if (node.val == val)
            return node;
        else if (val < node.val) {
            if (node.left == null)
                return null;
            else
                return recur(node.left, val);
        } else {
            if (node.right == null)
                return null;
            else
                return recur(node.right, val);
        }
    }
    
    public TreeNode searchBST(TreeNode root, int val) {
        return recur(root, val);
    }
}

Submission Detail

• 36 / 36 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in a Binary Search Tree.
• Memory Usage: 39.7 MB, less than 16.71% of Java online submissions for Search in a Binary Search Tree.

Problem

771. Jewels and Stones

Java

1

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

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> j = new HashSet<Character>();
        for(int i=0;i<jewels.length();i++)
            j.add(jewels.charAt(i));
        int n = 0;
        for(int i=0;i<stones.length();i++)
            if (j.contains(stones.charAt(i)))
                n++;
        return n;
    }
}

Submission Detail

• 255 / 255 test cases passed.
• Runtime: 1 ms, faster than 64.92% of Java online submissions for Jewels and Stones.
• Memory Usage: 37 MB, less than 89.30% of Java online submissions for Jewels and Stones.

Problem

1528. Shuffle String

Java

1

1
2
3
4
5
6
7
8
9

class Solution {
    public String restoreString(String s, int[] indices) {
        char[] t = new char[s.length()];
        for(int i=0;i<indices.length;i++) {
            t[indices[i]] = s.charAt(i);
        }
        return new String(t);
    }
}

Submission Detail

• 399 / 399 test cases passed.
• Runtime: 2 ms, faster than 28.58% of Java online submissions for Shuffle String.
• Memory Usage: 41.9 MB, less than 5.19% of Java online submissions for Shuffle String.

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.

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.

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.