Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 30 starting from zero "234. Palindrome Linked List"

Basically, I would like to solve the easy acceptance in descending order.

Twitter I'm doing it.

problem

581. Shortest Unsorted Continuous Subarray The difficulty level is easy. Excerpt from Top 100 Liked Questions.

The problem is given an array of integers. If you sort this array in ascending order, find contiguous subarrays that can sort the entire array in ascending order. The problem is to find the shortest sub array among them and return its length.

Let's consider an example.

Example 1: Input: [2, 6, 4, 8, 10, 9, 15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

If you sort in this, the entire array will be arranged in ascending order. The shortest sub-array is from 6 to 9, so the number of elements is acquired and 5 is returned.

solution

Prepare a sorted variable, a variable start that gets the element from the beginning, and a variable last that gets the element from the end, and if the values of the sorted array and the original array do not match, the index of that element is set. Substitute for start. Do it for last as well, and the difference +1 is the length of the required number of elements.

Finally, I implemented a function that returns last --start + 1 if last-start holds, and 0 otherwise.

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        start = last = 0
        num = sorted(nums)
        for i in range(len(nums)):
            if nums[i] != num[i]:
                start = i
                break
        for i in range(len(nums)-1,-1,-1):
            if nums[i] != num[i]:
                last = i
                break
        return last - start + 1 if last - start else 0
# Runtime: 196 ms, faster than 98.85% of Python3 online submissions for Shortest Unsorted Continuous Subarray.
# Memory Usage: 15.2 MB, less than 5.00% of Python3 online submissions for Shortest Unsorted Continuous Subarray.

It was a fairly simple idea, but it's better than I expected. The easy of Top Liked Questions has decreased considerably, so I feel that it will only be Medium in the future.

Regarding Hard, I don't know if it can be solved properly, but I will solve it if there is an opportunity.

[PYTHON] Let Code Day 31 starting from scratch "581. Shortest Unsorted Continuous Subarray"

Overview

problem

solution