Forem: Marcelo Surriabre

Leetcode: 2210. Count Hills and Valleys in an Array

Marcelo Surriabre — Mon, 29 Jan 2024 09:19:03 +0000

Introduction

In this series of "Leetcode" posts I will publish solutions to leetcode problems. It is true that you can find most/lots of leetcode solutions on the web, but I will try to post my solutions to problems that are interesting or to problems for which the solutions out there are not well explained and deserve a better explanation.

The aim is to share knowledge, and that people who are studying, preparing for interviews, or just practicing, can become better at solving problems. Please feel free to comment if you have a suggestion or a different approach!

Problem link

Count hills and valleys

Problem statement

You are given an array and you have to find hills and valleys.

The idea is simple yet a bit complex, I will just copy/paste from leetcode which is
already quite verbose but helps to fully understand the problem.

Example:

Input: nums = [2,4,1,1,6,5]
Output: 3
Explanation:
At index 0: There is no non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley.
At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill.
At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley.
At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2.
At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill.
At index 5: There is no non-equal neighbor of 5 on the right, so index 5 is neither a hill nor a valley.
There are 3 hills and valleys so we return 3.

Solution

This problem despite being "easy" took me some time to solve.
I had to sleep over it to find an extremely quick solution next day :)
Sometimes you just gotta rest.

Important considerations

One of the most challenging parts of this problem is the fact that you could have duplicates:

1,2,2,2,8 -> This has one Hill

This means that you have to "ignore" the adjacent equal vales and only consider the values that are different

Another important constraint or issue, is that at the beginning of the array you don't know if you are going up or down.

Approach 1

At any point in time, you will be either "Up" or "Down"
Except in the beginning, as you don't have previous value for the first value of the array
If you are going UP and then go down, meaning you find that the next value is less than the current value , then that means you have found a Hill.
If you are going DOWN and then go up, meaning you find that the next value is larger than the current value , then that means you have found a Valley.


public int countHillValleyWithFlag(int[] nums) {
    int valleys = 0;
    int hills = 0;
    int index = 1;
    // Find first non-repeating value
    while (index < nums.length && nums[index] == nums[index - 1]) {
        index++;
    }
    if (index == nums.length) return 0;

    boolean isUp = nums[index] > nums[index - 1];
    while (index < nums.length) {
        int cur = nums[index];
        int prev = nums[index - 1];
        if (cur > prev) {
            if (!isUp) {
                hills++;
                isUp = true;
            }
        } else if (cur < prev) {
            if (isUp) {
                valleys++;
                isUp = false;
            }
        }
        index++;
    }
    return valleys + hills;
}

We have to find the first non-repeating value, this is because we have to know if we are UP or DOWN, if the values are the same, we don't know this fact.
Once we know if we are going UP or DOWN, then we can check:
- If current > prev && !isUP(down): If we were going DOWN and the current value is greater than previous, we have found a Valley */
- If current < previous && isUP: If we were going UP and the current value is less than previous, we have found a Hill /*\

Approach 2

Notice that for a Hill or Valley we have neighbour values that should be different to the current value.
Key fact : The surrounding values have both to be greater or less than the value in the middle.
Picture this hill: 10, 30, 20
Picture this valley: 30, 10, 50
We have to find the neighbour/surrounding values. And if they comply to the above-mentioned statements then we found a valley/hill.

public int countHillValleyNeighbours(int[] nums) {
    int prev = nums[0];
    int hills = 0;
    int valleys = 0;
    for (int i = 1; i < nums.length - 1; i++) {
        int cur = nums[i];
        int next = nums[i + 1];
        if (next != cur) {
            if (prev > cur && next > cur) valleys++;
            else if (prev < cur && next < cur) hills++;
            prev = cur;
        }
    }
    return hills + valleys;
}

We have to ignore similar values, for instance:
1,2,3,3,3,4,5
At index 4, we cannot say "3" is the previous values, remember that we are looking for
values/neighbours that are different to the actual value.
We basically want to simplify to this:
1,2,3,4,5
So the actual neighbours of 3 are 2 and 4.
To do this we just have to be sure that the "next" value is different that the "current"
and then we can replace the old previous value with the current one.

Complexity

Time complexity

In both approaches we just have to go through the array one time Therefore:
O(n) : Linear to the input size

Space complexity

We don't make use of any other data structure. We simply use some variables. Therefore:
O(1) Constant space, as it does not depend on the input size

Final comments:

This was a tricky task but fun to do it.
It is a good idea to analyze the requirements in concrete terms.
In this case: what it means a hill or a valley?
If you can put those into words then you already have an algorithm to solve it.

Leetcode: 556. Next Greater Element III

Marcelo Surriabre — Wed, 23 Dec 2020 17:18:24 +0000

Introduction

Problem statement

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.

Solution

The main idea

Start from the "end" of the number/digits.
Find the indexes of the digits to swap in order to make the number greater.
Swap the indexes.
Sort the digits starting at swap index + 1.
Create the new number.

Explanation and Code

The idea is to create a new number that is greater than the original number. But with the constraints that the new number must:

Be the next smallest number
Have the same digits

Basically you have to re-position the digits in such way that they are arranged to comply with the constraints. If there is not such number just return -1.

The second constraint: Have the same digits, helps to understand that there is no need to add/remove any digits. We just need to play with the digits we already have.

First Idea: Permutation

If all it takes is to re-arrange, then you can be thinking: Permute. You can try to permute (complexity O(n^2)), and take the next greater number out of all the possible arrangements, but the complexity is not optimal at all. Quadratic complexity is most of the time the worst possible possible solution in these types of problems, and most likely not a viable solution.So we have to think of something else.

Second Idea: Find and swap digits

We must find the next greater number with the digits we have. So we have to think what would be the next smallest number.

The example provided gives an idea:

Input: n = 12
Output: 21

The first thing you could be thinking is:

Find the next greatest digit that is greater than the first digit and swap them

That is not correct!. Let's see why.

For example if have:

Input: n = 54281

The first digit is: 5
The next greatest digit: 8

If you swap the digits you obtain:

Output: 84251

That is not the next greater number. The next greater number would be:

54821

You can create more examples. But at the end, you would realize that you need to start from the end of the number and not from the start of it.

Now it comes down to something simple:

Find the digit to replace

So which digit is that?.

You have to think what would make a number greater than another. The best way is to think of a 2 digit number:

35 => 53

So the first digit is 3, which is in the tens place. To make this number greater we would need to swap it with any digit greater than 3, that means any of {4,5,6,7,8,9}. But we only have 5, so we choose 5 and swap it.

But what happens if we have a bigger number, with more than 2 digits. I find it helpful to divide the number in 2 parts. You take a "digit" and you have all the digits before it and all the digits after it. For example:

Number: 823475321

We can take the digit: 4
Digits before: 823
Digits after: 75321

If we want to replace 4 we don't really care about the numbers before it, at least for now.

We want to find a number greater than 4, that is part of digits after 4, that means picking a digit from {7,5,3,2,1}. We must choose the next greatest digit, that means picking up 5, and then swap it:

Number: **823574321

Great we have a number greater than the original. But wait! That is not the next greater number. Look carefully, you can notice that we can arrange the numbers after the original digit(4), and create a smaller number. That means:

Take the digits after 5(the swapped digit) : 74321.
Now re-arrange them to get a smaller number: 12347

With this example it is easy to see how we should arrange those digits. Just sort them! Why?. Because if you sort them, it will put the smallest digit first, and then the next smallest, and so on. At the end you will obtain the smallest possible number with those digits.

It seems that we have a strategy, but the most important part is missing, how to find the digit to swap, in this example that was the number 4.

Find the number to Swap

We follow the same logic. Let's take the same example:

Number: 823475321

Start from the end. That means take the last digit 1.
But we cannot replace the last digit with anything, there is nothing after it, so move the left.
We pick 2. We search in the digits after it: {1}. There are no greater digits, so we keep moving to the left.
We pick 3. We search in the digits after it: {2,1}. There are no greater digits, so we keep moving to the left.

...We do the same until we reach 4

We pick 4. We search in the digits after it: {7,5,3,2,1}. Now we have numbers that are greater than 4, those are {7,5}, we pick the next greater number, that means 5.

Did you notice something? We kept moving as long there was no number greater than the current digit, on the numbers to its right or after it. So that's it, that is the algorithm:

Start at position: end - 1
Move to the left, until there is a number greater to the current digit in the digits to its right.

The code may look like this:

    private int skipUntilDigitGreaterFound(char[] digits) {
        int index = digits.length - 2;
        while (index >= 0) {
            addDigitToSeenDigits(digits[i+1]);
            if (existsDigitGreaterThanCurrentInSeenDigits()) break;
            index--;
        }
        return index;
    }

But there is a big problem with this approach. The searching in the digits to the right of the current digit is the problem.

You can do a linear search (O(n)) in the seen set. Or you can take advantage of the fact that digits to the right must be sorted in the reverse order, this is a key fact to realize, and do a inverted binary search(O(log(n)).

But there is an even better approach in constant time: O(1)!

The idea is simple:

We are dealing with digits, we have a constant amount of digits: 10.
The only thing we care is finding the next bigger digit. So if we have the digit 4, we are looking if we have seen (digits to the right of 4 in the original number) a number greater than 4, which could be {5,6,7,8,9}.
So we can create an array of 10 elements(0 to 9) called: digitsPositions, where the index represents each digit, and the value represents the last found position of each digit.
When we want to find the position of a digit greater than a another, for instance: 4, we simple start at immediate next digit: 5, and see if there is some value set in the digitsPositions array for that index 5. If there is, that means we already saw that digit, and that's it we have the next bigger digit. If not, we keep on searching with the next digit: 6 and so on.
At most we would do a search for 10 elements (from 0 to 9) in the array. That means, constant time for searching.

In code we have something like this:


    // Skip method, saves every "seen" digit in the digitsPositions array.
    private int skipUntilDigitLessThanNext(char[] digits) {
        int index = digits.length - 2;
        while (index >= 0) {
            digitsPositions[digits[index + 1] - '0'] = index + 1;
            if (digits[index] < digits[index + 1]) break;
            index--;
        }
        return index;
    }

    private int findGreaterIndex(int digit) {
        for (int greaterDigit = digit + 1; greaterDigit < this.digitsPositions.length; greaterDigit++) {
            if (digitsPositions[greaterDigit] > 0) return digitsPositions[greaterDigit];
        }
        return -1;
    }

Notice that if have seen multiple times a digit we only save the last occurrence in the digitsPositions array. This does not matter at all because at the end we only care about finding that greater value and some index to replace with. After that the digits to the right of the swap are going to be sorted so no issues at all.

The complete solution

    private final int[] digitsPositions = new int[10];

    public int nextGreaterElement(int n) {
        if (n < 10) return -1;
        return findAndCreateNextGreaterElement(convertNumberToCharArray(n));

    }

    private char[] convertNumberToCharArray(int n) {
        return String.valueOf(n).toCharArray();
    }

    private int findAndCreateNextGreaterElement(char[] digits) {
        int indexToSwap = skipUntilDigitLessThanNext(digits);
        if (indexToSwap < 0) return -1;
        int digit = Character.getNumericValue(digits[indexToSwap]);
        int greaterIndex = findGreaterIndex(digit);
        return createNextGreaterNumber(digits, indexToSwap, greaterIndex);
    }

    private int skipUntilDigitLessThanNext(char[] digits) {
        int index = digits.length - 2;
        while (index >= 0) {
            digitsPositions[digits[index + 1] - '0'] = index + 1;
            if (digits[index] < digits[index + 1]) break;
            index--;
        }
        return index;
    }

    private int findGreaterIndex(int digit) {
        for (int greaterDigit = digit + 1; greaterDigit < this.digitsPositions.length; greaterDigit++) {
            if (digitsPositions[greaterDigit] > 0) return digitsPositions[greaterDigit];
        }
        return -1;
    }

    private int createNextGreaterNumber(char[] digits, int indexToReplace, int greaterIndex) {
        swap(digits, indexToReplace, greaterIndex);
        Arrays.sort(digits, indexToReplace + 1, digits.length);
        try {
            return Integer.parseInt(new String(digits));
        } catch (NumberFormatException exception) {
            return -1;
        }
    }

    private void swap(char[] digits, int currentIndex, int replaceIndex) {
        char temp = digits[currentIndex];
        digits[currentIndex] = digits[replaceIndex];
        digits[replaceIndex] = temp;
    }

Complexity

Time: O(n) + O(nlog(n)), in the worst case we would have to go all the way to the first digit, remember we start from the end, that would be the O(n). After the swap, we need to sort the numbers to the right, and in the worst case the swap position would be 0, again at the start, so that would be O(n(log(n)).

We are only going to search through the digitsPositions once, and that is O(1).

Space: O(1), we are only creating a the digitsPositions array, of size 10.

Another solution:

This was a very interesting problem, where there are many interesting parts to analyze before coming up with the most optimal solution. Again this problem can be one of the divide and conquer, where we split the bigger problem in smaller ones, in this case: find the swap digit and search for the greater digit. Usually it is useful to think in smaller cases and go from there. That helped me a lot for coming up with this solution.

Android RxJava Reducer with the Visitor Pattern

Marcelo Surriabre — Mon, 26 Oct 2020 21:03:12 +0000

Introduction

It is always a good idea to work on different projects and different technologies, as it provides a good source of knowledge for different parts of components of applications. Technologies used in the Frontend do not usually use the same tools or concepts as technologies on the Backend, and that is precisely the reason why working on both is a good idea. You can incorporate some ideas from one to the other. With this experience, in this article I develop a “RxJava Reducer” that can be used in Android applications.

The code

All the app code is in the repo:

Recycler State

Main Idea

The idea is simple:

We have an activity where the user triggers some action, such as clicking on an element, and as a result we move into another activity, the destination activity, in order to show the result of that action. The actions are usually async actions (database calls, api calls, etc.) that fetch some data that is going to be displayed to the user.

This process can involve different states on the destination activity. For instance, we could have the following states:

Loading
Loaded
Error

We need to update the state of the destination activity according to the result of the async action.

RxJava is used for processing the async actions and to manage the subscription of the destination activity, so it can be updated with the results of the async call.

Libraries/Dependencies

The following are the main dependencies that are used:

RxJava for handling async calls
Room for database
Navigation component for application flow
ViewModel to manage UI data
LiveData to handle the data on the ViewModel
Hilt for dependency injection
Java 8+ (Desugaring for using Java8+ API, full lambda!)

Application architecture

Single activity app. Given the recent updates on the android environment, it is recommended to use this new architecture for apps.

I recently had the experience of migrating a multi activity application to a single activity app and it wasn’t pain free. I think most of the time went into deciding how to move code out of the activities and how to structure the application using the navigation graphs. This was an important step as I decided to jump into all new android architecture components. Meaning: single activity app + architecture components (room, livedata, viewmodel) + navigation components. Before the migration, my app only had Room database, none of the other new features.

You can read more about these concepts here: Android Architecture Components

I have to say that I really liked the final product. Using all these tools really forces you to think in terms of the architecture of your app and how you organize the code. The result is usually a very clean code/architecture with separation of concerns which makes it easy to change/update your app in the future. But you will probably have to spend a good amount of time understanding what works best for your specific functionality in your app and also reading a lot about the different ways you can conceive what you want using these new tools.

UI/View model

The app uses a typical pattern that you can see in almost any app: Master/Detail, but it seems this has been renamed to Primary/Detail Flow. I will use the terms master/detail as you can find much more information on the web under this name.

Basically you have a master view with a list of items. And when you click on one item you go to another view that displays the specific information of that item, that is the detail view.

Mapping of concepts

There is no exact mapping between the concepts of Redux to Android but we can define some similarities according the the main function of the concepts.

1. Store

The application state resides in the ViewModel. The ViewModel is the closest in terms of the Redux store, it handles the actions, which in turn can call an API or database.

2. Action

These are defined as methods within the ViewModel. For instance, the loadItem method. Any other components in the application can call(dispatch) these methods in the ViewModel.

public class ItemsViewModelImpl extends ViewModel {
    public void loadItem(long itemId) {
        setItemDetailState(ItemDetailLoadingState.getInstance());
        removeSubscriptionFromCompositeDisposable(getItemSubscription);
        getItemSubscription = itemRepository.getItem(itemId)
                .delay(2, TimeUnit.SECONDS)
                .subscribeOn(Schedulers.io())
                .observeOn(AndroidSchedulers.mainThread())
                .subscribe(
                        this::onItemLoaded,
                        onItemDBError(DBOperation.GET)
                );
        compositeDisposable.add(getAllItemsSubscription);
    }
}

As you can see we use RxJava for handling the async calls. In this sense we can say that RxJava takes the place of the Thunk function.

3. Reducers

These are defined as methods within a Fragment. The ListDetailFragement. Which also acts as a subscriber of the changes. This is a main difference in respect to Redux, where a reducer is defined independently of the component that uses the result of the reduction process.

4. State

The state is modeled using Polymorhphism. There is an interface named “ItemDetailState’ which has 3 different implementations: ItemDetailErrorState, ItemDetailLoadingState, ItemDetailLoadedState. This is explained in detailed in the next section. Just keep in mind we have the following classes:

IItemDetailState (Interface)
ItemDetailErrorState
ItemDetailLoadingState
ItemDetailLoadedState

Reduction and update of the state of the application

Now here comes the fun part. Usually with Redux we would have a function with a switch statement to define the reducer. But instead of using a plain switch statement we can use one of the most powerful tools in object oriented programming: “Polymorphism”. Not only that but we can use a very “rare” pattern: “The visitor pattern”.

The main problem we have is the following:

We have a list of items in the ListMasterFragment, and we want to see the data of a specific item in the ListDetailFragment.

However we need some data to update the view of the ListDetailFragment, this is the data of a specific Item.

The data is not in the ListDetailFragment. The data is in the ItemDetailState.

The ItemDetailState is an interface representing the state of an Item in the view, therefore, we may have multiple implementations, each with different state. We need to handle each state differently.

Solution

1st Idea

Use “instanceOf”(similar to the switch statement to reduce in Redux) to determine the actual type of the ItemDetailState implementation and get the required data.

The drawback of this approach is that we would need to update the instance of with more states whenever we add a new state. Needless to say, having multiples if or switch statements is a code smell. Moreover, we can actually bypass or forget to handle a new state. We are not enforcing correct behaviour and this could lead to bugs.

2nd idea: The Visitor Pattern

We can use the Visitor Pattern to solve our problems. If you need to know more about the pattern you can read a good introduction here:

Visitor Pattern

As with all the patterns, they serve as a guideline to solve common problems. Each problem is different and you can use the patterns as you may seem appropriate. In this case we are not using all the advantages of the pattern,such as the double-dispatch, as we only need to use polymorphism at the method argument level, not the receiver level.

You can read more about the double dispatch here: Visitor Pattern - Double dispatch

The implementation of the Visitor Pattern for the reducer is done in the following steps:

We start by defining the Visitor interface:

public interface ItemDetailVisitor {

    void handleItemDetailLoadingState(ItemDetailLoadingState itemDetailLoadingState);

    void handleItemDetailLoadedState(ItemDetailLoadedState itemDetailLoadedState);

    void handleItemDetailErrorState(ItemDetailErrorState itemDetailErrorState);
}

The ListDetailFragment implements this interface:

public class ListDetailFragment extends Fragment implements ItemDetailVisitor {

    @Override
    public void handleItemDetailLoadingState(ItemDetailLoadingState itemDetailLoadingState) {
        showProgressBarLoading();
    }

    @Override
    public void handleItemDetailLoadedState(ItemDetailLoadedState itemDetailLoadedState) {
        setItemDetailData(itemDetailLoadedState);
        setItemDataOnView();
        hideLoadingProgressBar();
        Snackbar.make(requireView(), R.string.toast_loaded_successfully, Snackbar.LENGTH_SHORT).show();
    }

    @Override
    public void handleItemDetailErrorState(ItemDetailErrorState itemDetailErrorState) {
        hideLoadingProgressBar();
        Toast.makeText(getActivity(), R.string.toast_error_loading_item, Toast.LENGTH_SHORT).show();
    }
}

We subscribe to changes on the ItemDetailState, which we get using the subscription provided by RxJava. This data is handled in the ViewModel using LiveData:

    private void setItemData() {
        itemsViewModel.getItemDetailState().observe(getViewLifecycleOwner(), this::onItemDetailStateChange);
    }

    private void onItemDetailStateChange(IItemDetailState itemDetailState) {
        itemDetailState.accept(this);
    }

4. We define the abstract accept method on the IItemDetailInterface:

public interface IItemDetailState {
    void accept(ItemDetailVisitor itemDetailVisitor);
}

5. Finally we implement the accept method on the concrete classes:

// On the ItemDetailStateError
    @Override
    public void accept(ItemDetailVisitor itemDetailVisitor) {
        itemDetailVisitor.handleItemDetailErrorState(this);

// On the ItemDetailLoadedState
    @Override
    public void accept(ItemDetailVisitor itemDetailVisitor) {
        itemDetailVisitor.handleItemDetailLoadedState(this);
    }

// On the ItemDetailLoadingState
    @Override
    public void accept(ItemDetailVisitor itemDetailVisitor) {
        itemDetailVisitor.handleItemDetailLoadingState(this);
    }

In order to understand better how the problem is solved we can take a look at the data flow of the application.

Data flow

An item on the list is selected. ListMasterFragment triggers the loading of the selected item in the ViewModel and moves the view to the ListDetailFragment:

    @Override
    public View.OnClickListener seeItemButtonListener(ItemsRecyclerViewAdapter.ItemViewHolder holder, Item item) {
        return view -> goToItemDetail(view, item);
    }

    private void goToItemDetail(View view, Item item) {
        itemsViewModel.loadItem(item.getId());
        NavDirections toItemDetail = ListMasterFragmentDirections.actionListMasterFragmentToListDetailFragment();
        Navigation.findNavController(view).navigate(toItemDetail);
    }

The ItemsViewModel receives the call to load the item and updates the ItemDetailState to "Loading", meanwhile, it does an async call to get the item details:

    public void loadItem(long itemId) {
        setItemDetailState(ItemDetailLoadingState.getInstance());
        removeSubscriptionFromCompositeDisposable(getItemSubscription);
        getItemSubscription = itemRepository.getItem(itemId)
                .delay(2, TimeUnit.SECONDS)
                .subscribeOn(Schedulers.io())
                .observeOn(AndroidSchedulers.mainThread())
                .subscribe(
                        this::onItemLoaded,
                        onItemDBError(DBOperation.GET)
                );
        compositeDisposable.add(getAllItemsSubscription);
    }

The setItemDetails is as follows:

    private void setItemDetailState(IItemDetailState itemDetailState) {
        this.itemDetailStateLiveData.setValue(itemDetailState);
    }

Basically it updates the LivaData instance variable, which will notify any subscriber of this LiveData. Remember that the ListDetailFragment is subscribed to this LiveData:

// On the ListDetailFragment

    private void setItemData() {
        itemsViewModel.getItemDetailState().observe(getViewLifecycleOwner(), this::onItemDetailStateChange);
    }

    private void onItemDetailStateChange(IItemDetailState itemDetailState) {
        itemDetailState.accept(this);
    }

So it will call the "accept" method on the "ItemDetailStateLoading" with the ListDetailFragment as an argument. Because this method is polymorphic on the argument type, it can call any concrete implementation of the interface! In this case the concrete implementation is the ItemDetailLoadingState.

The ItemDetailLoadingState receives the call and calls the corresponding method on the ListDetailFragment, which implements the ItemDetailVisitor interface:

// On the ItemDetailLoadingState
    @Override
    public void accept(ItemDetailVisitor itemDetailVisitor) {
        itemDetailVisitor.handleItemDetailLoadingState(this);
    }

The ListDetailFragment calls the handleItemDetailLoadingState method:

    @Override
    public void handleItemDetailLoadingState(ItemDetailLoadingState itemDetailLoadingState) {
        showProgressBarLoading();
    }

After some time, the result is obtained from the RxJava async call on the ViewModel:

    private void onItemLoaded(Item item) {
        setItemDetailState(ItemDetailLoadedState.of(item));
    }

This will again update the LiveData, but this time with an instance of the ItemDetailLoadedState, which contains the data of the item that was loaded.

Again, the ListDetailFragment receives the update and calls the "accept" method, but this time in the ItemDetailLoadedState, thanks to the polymorphic method ":


// On the ListDetailFragment

    private void onItemDetailStateChange(IItemDetailState itemDetailState) {
        itemDetailState.accept(this);
    }

// On the ItemDetailLoadedState
    @Override
    public void accept(ItemDetailVisitor itemDetailVisitor) {
        itemDetailVisitor.handleItemDetailLoadedState(this);
    }

Finally, the ListDetailFragment handles the call, and updates the View:

   @Override
    public void handleItemDetailLoadedState(ItemDetailLoadedState itemDetailLoadedState) {
        setItemDetailData(itemDetailLoadedState);
        setItemDataOnView();
        hideLoadingProgressBar();
        Snackbar.make(requireView(), R.string.toast_loaded_successfully, Snackbar.LENGTH_SHORT).show();
    }

Basically we define the handler methods on the Visitor interface, and the implementation, in this case the ListDetailFragment decide how to implement them, updating the view according to the state.

With this approach, we can leverage the polymorphic types of the state and provide a solid architecture that handles beautifully the changes in the view.

Conclusions

This was a small proof of concept of how you can use the idea from other frameworks/libraries in different part of an application. In this case I took the Reducer idea from Redux, a frontend library, which can be quite useful for handling state changes using async calls in an Android application.

There might be better approaches but I found this one particularly interesting because it makes use of polymorphism to solve the reduction problem of multiple states.

I am planning on making several articles based on the same app as it has several interesting implementation details. For instance why using an interface for the State istead of having one state with "type" as a field. Also the RxJava subscription handling.

Trie Data structure with Design Patterns

Marcelo Surriabre — Mon, 28 Sep 2020 19:32:49 +0000

Introduction

In this post I am gonna show how you can implement the Trie data structure using different design principles and patterns. This idea came to me after implementing the Trie data structure and trying different algorithms.

The final result shows as a very good use case of the application of different design patterns and principles, and the benefits of using them.

The code

Full code is available on github: Trie data structure

The data structure

The Trie data structure is also called Prefix tree, as the main goal of this data structure is to provide an easy way to search for strings based on the characters of the strings, going one by one, basically, searching by the prefix.

This data structure has many application such as autocomplete and spell checker. I find the a very good explanation of the possible usages on the solution of leetcode: Trie leetcode solution.

I am not going to focus on the implementation of the algorithm itself. You can find the implementation basically anywhere. In case you want to do it yourself I recommend Tushar Roy on youtube: Tushar Roy - Trie. I based my solution on his explanation (not on his solution). So you can even see his implementation if you want to compare.

Classes and interfaces

The code is organized in 3 different packages:

trie
node
algorithm

The trie package

The ITrie interface

The trie data structure is represented using an interface, the ITrie interface.

This interface defines the basic behavior of the trie data structure:

void setTrieAlgorithm(ITrieAlgorithm trieAlgorithm);
ITrieAlgorithm getTrieAlgorithm();
ITrieNode getRoot();
void insertWord(String word);
boolean deleteWord(String word);
boolean containsWord(String word);
boolean containsPrefix(String prefix);

These abstract methods should be implemented by any class that wants to act as a Trie.

The first 3 methods provide means for composition and decoupling the Trie from the trie algorithms.

Notice the "setTrieAlgorithm" method, which allows to change at runtime the algorithm of the Trie.

The ITrie implementations

There are 2 different implementations for the ITrie interface:

TrieArray : Uses an Array-based node
TrieMap : Uses a Map-based node

The name of the implementations derive from the fact that they are using a specific type of TrieNode. For instance, the TrieArray implementaion uses a TrieNodeArray as they type of node for the trie data structure.

These nodes use a specific data structure, such as Array and Map, to store the different characters in each node.

The ITrie interface defines a method to change the trie algorithm at runtime. This is accomplished using composition of classes. The trie implementation is composed with a trie algorithm that is the one in charge of actually doing the different operations.

With this, the implementations of the methods that provide the behavior for the interface are quite simple:

 @Override
    public void insertWord(String word) {
        trieAlgorithm.insertWord(this, word);
    }

    @Override
    public boolean deleteWord(String word) {
        return trieAlgorithm.deleteWord(this, word);
    }

    @Override
    public boolean containsWord(String word) {
        return trieAlgorithm.containsWord(this, word);
    }

    @Override
    public boolean containsPrefix(String prefix) {
        return trieAlgorithm.containsPrefix(this, prefix);
    }

The implementations use delegation, to pass the responsability of the action to the composed trie algorithm. This makes sense, as the actual operation depends on the algorithm.

The trie algorithm is injected in the constructor:

    public TrieArray(ITrieAlgorithm trieAlgorithm) {
        setTrieAlgorithm(trieAlgorithm);
        this.root = new TrieNodeArray();
    }

    @Override
    public void setTrieAlgorithm(ITrieAlgorithm trieAlgorithm) {
        this.trieAlgorithm = trieAlgorithm;
    }

This is the constructor of the TrieArray, and the one in the TrieMap is similar.

The constructor receives an algorithm with the type of the interface ITrieAlgorithm, and assigns to the field "trieAlgorithm" using the corresponding method.

Using an interface as the type of the algorithm and assignin it in the constructor allows to use dependency injection, which is a mechanism to implement the Dependency Inversion Principle. Notice that we are also applying the design principle : "program to interfaces, not to implementations".

This provides means for decoupling the Trie data structure from the inner details of the algorithm. The implementations of the ITrie interface, do not really know or care about the implementations of the ITrieAlgorithm interface. All the Trie cares about is the behavior of those implementations.

You should try to encapsulate and group things according to the axis of change. You group together things that change for the same reasons and at the same rate. In this case, the Trie data structure is a very stable component, and its interface along with the implementations will not likely change that often. On the other side, we have the different algorithm implementations, which can change quite often. For instance, you decide to change some inner details of the algorithm, such as the recursive calls, or the use of some inner data structure within the algorithm. These changes should not affect the Trie data structure at all.

The strategy pattern
This definition is taken from the Head First Design Patterns book (excellent book!):

"The Strategy Pattern defines a family of algorithms,
encapsulates each one, and makes them interchangeable.
Strategy lets the algorithm vary independently from
clients that use it."

In this case, we define a family of algorithms with the ITrieAlgorithm interface.

The different implementations: Iterative, Recursive, Recursive2, can be used interchangeably. This is great! We encapsulated the parts that changed into an specific interface. Now the client or whoever uses the Trie data structure, doesn't depend on any specific implementation. If you come up with a new better way to implement the algorithm you just have to implement the interface and that's it. You can replace, with the setter method, and your new algorithm will be used by the Trie. No need to change absolutely anything on the Trie class!

The ITrieAlgorithm interface

This interface defines the common behavior that any trie algorithm should have:

public interface ITrieAlgorithm {

    void insertWord(ITrie trie, String word);

    boolean deleteWord(ITrie trie, String word);

    boolean containsWord(ITrie trie, String word);

    boolean containsPrefix(ITrie trie, String prefix);
}

The important thing to notice in the method's signature is the ITrie argument. The algorithms don't need to know or care about the actual details of the implementation of the Trie data structure, all they care is that they implement the ITrie interface, and more specifically that they provide implementation for the getRoot method, as we will see in the next section.

The ITrieAlgorithm implementations

The are 3 different implementations of the ITrie interface:

TrieIterativeAlgorithm
TrieRecursiveAlgorithm
TrieRecursiveAlgorithm2

The names are self-descriptive. We have 1 algorithm that uses an iterative approach using loops. And the other ones use a recursive approach.

Let's take a look into the implementaion for the "insertWord" method:

    /**
     * Insert a word in the trie
     *
     * @param trie The Trie where the word will be inserted
     * @param word The word to insert
     */
    @Override
    public void insertWord(ITrie trie, String word) {
        insertWord(trie.getRoot(), word);
    }

    /**
     * Helper method that inserts the word in the Trie.
     * This algorithm sets the "isEndOfWord" flag to the trieNode that the last character points.
     *
     * @param trieNode The trieNode to insert the character
     * @param word     The word to insert
     */
    private void insertWord(ITrieNode trieNode, String word) {
        char currentChar;
        for (int i = 0; i < word.length(); i++) {
            currentChar = word.charAt(i);
            if (!trieNode.containsCharacter(currentChar)) {
                trieNode.addCharacter(currentChar);
            }
            trieNode = trieNode.getTrieNodeForChar(currentChar);
        }
        trieNode.setEndOfWord(true);
    }

The insertWord method receives the trie as an argument with the ITrie type. The algorithm doesn't care about the inner implementaion, it just gets the root node through the getRoot method, and proceeds with the operation.

Now take a look into the helper method. It receives the node with the interface type of ITrieNode. Again, the algorithm doesn't really care how the nodes are actually implemented. Whether it uses an array or a map, the algorithm is the same. This a very important detail, because the algorithm is completely decoupled from the implementations of the Trie and Nodes. It can operate on any implementation. These means that we can reuse the same algorithm for different instances of Trie implementation.

Summary of Design patterns and principles applied

Encapsulate what varies: The actual implementation of the algorithm.
Favor composition over inheritance: The Trie data structure uses a "composed" algorithm, which is passed in the constructor.
Program to interfaces, not to implementations: The ITrie, ITrieNode and ITrieAlgorithm are interfaces that are used in the different implementations. No reference or dependency on any specific implementations. This means that the different components are decoupled and be modified independently.
Open/Closed principle: Whenever there is a change in your algorithm, the Trie data structure doesn't really care, as it doesn't depend on the implementation, you can modify or create a whole new algorithm, and you won't have to change a thing in the Trie data structure class! The same goes for the other way around. You can change your data structure in the Trie, and the algorithm will still work on your new Trie. Obviously, all of this is possible through the interfaces defined for each class. As long as implementations adhere to those contracts, everything should be fine.
Depend upon abstractions. Do not depend upon concrete classes: We applied the dependency inversion principle as we inverted the source code dependency from the Trie to the concrete algorithm implementations. Now both the Trie and the Algorithms depend on abstractions. The Trie doesn't know about any concrete implementation of the Algorithm, it just uses the interface. The same for the Algorithms. Any implementation of the algorithm does not depend on any concrete implementation of the Trie/TrieNode, it only depends on abstractions, the ITrie and the ITrieNode.

Final words

This was as simple example of how you can apply different design principles and patters to common tasks, such as creating your own algorithm implementations based on defined data structures. Applying the different design principles provides lots of benefits as the ones presented in this article.

Leetcode: 994. Rotting Oranges

Marcelo Surriabre — Sun, 09 Aug 2020 21:27:38 +0000

Introduction

Problem statement

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

You can see the examples and more information on the leetcode problem page.

Solution

Always try to solve the problems yourself instead of looking at the solutions on leetcode or the web. Once you see the answer, you tend to thing that those solutions are the only approach to solve the problem and you stop thinking about other possible solutions. For instance, most of the solutions I've seen use BFS, which seems like a good choice given the idea of "time", and you simulate the time passing and rotting the oranges.

However, looking at the grid, I came up with a different approach using DFS, which seems to be faster(100%) than the other proposed solutions(around 80%).

Main idea

If you look at the grid of oranges, you realize that the time it takes for a fresh orange to rotten is the minimum distance from any rotten orange to that fresh orange. Basically, one movement in the grid, whether it is vertical or horizontal, counts as 1 minute.

In general terms you need to do the following:

For each fresh orange you need to find the minimum distance to a rotten orange among all the rotten oranges.
Once you set the minimum distance of all fresh oranges, you go through all the minimum distances and pick the maximum among all of them. This is because the largest distance will dictate the minimum time it will take to rotten.

For instance, if you have the following minimum times/distances:

{12,54,23,21}

The maximum of them is 54. This means that it will take 54 minutes to rotten all the oranges. If we would pick the minimum, which is 12, then after 12 minutes, only that orange would be rotten, but rest are not!. That is why we must take the largest of those values to make sure all of the oranges will be rotten by that time. So by minute 54, we are sure all the oranges are rotten.

Rather than creating a map or some other data structure, we can just reuse the current grid to set the distance/time to each fresh orange. So each grid cell will contain the minimum distance to a rotten orange(only if it is fresh).

For the solution I used a functional approach, in the sense that I divided the solution into method(functions), where each function does one specific thing. Always try to code this way!

As the solution is a bit large, I am gonna split the code in several parts, explaining each part and then show the whole solution.

The main method


private static final int FRESH = 1;
private static final int ROTTEN = 2;
public static final int TIME_OFFSET = 3;
public static final int CANNOT_BE_ROTTEN = -1;

public int orangesRotting(int[][] grid) {
        setMinTimeToRotten(grid);
        int maxTime = getMaxTimeToRotten(grid);
        if (maxTime == CANNOT_BE_ROTTEN) return CANNOT_BE_ROTTEN;
        return Math.max(0, maxTime - TIME_OFFSET);
    }
}

First we set the minimum time to rotten all the fresh oranges, with the "setMinTimeToRotten" method.

Then we get the max time to rotten among all the minimum times.

Finally we return the result based on the maxTime found. I used an offset here that I will explain in detail with the "setMinTimeToRotten" method.

setMinTimeToRotten method

private void setMinTimeToRotten(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == ROTTEN) {
                    dfsInAllDirections(grid, i, j, 1 + TIME_OFFSET);
                }
            }
        }
    }

This is just the nested for loop to go through the whole grid. The important part happens whenever we find a ROTTEN orange. In that case we do a DFS (Depth First Search), with the Offset. The "dfsInAllDirections" method is just a helper method that goes into all possible directions, horizontally and vertically.

dfs method

    private void dfs(int[][] grid, int i, int j, int time) {
        if (!isValid(grid, i, j) || !isFresh(grid[i][j])) return;
        int originalOrangeValue = grid[i][j];
        grid[i][j] = -1;
        dfsInAllDirections(grid, i, j, time + 1);
        grid[i][j] = getMinTimeToRotten(time, originalOrangeValue);
    }

This is the most important method, and where all the logic occurs.

First we check that the grid position, defined by i and j, is valid, meaning it is within the limits of the grid. Then we also need check that the position at grid[i][j] is fresh. If it is not a fresh orange, then we cannot do anything, we are only looking for fresh oranges.

Once we pass this check, we know for sure that we have a fresh orange at position grid[i][j]. So we need to update the distance of this fresh orange. And here is the reason we need an offset.

Because we are reusing the same grid and we are updating the values of each grid, we need to be careful with its value. For instance:

The initial value of a fresh orange will be: "1"
If we update the value with the new distance, let's say "2", then the value of that grid will be "2". This can be confused with a "rotten orange". So in order to avoid this problem we set an offset, so we start with a value of that offset. I set it to "3" for my solution. This means that fresh oranges will be updates with values greater than 3.

But before we set the value for this grid, we need to "mark it" somehow so we don't pass again through the same grid position when doing the DFS. That is why the grid is set to -1.

Then we do again the DFS, from that grid position to search for all possible reachable fresh oranges. Every DFS, we add the "time + 1", meaning it is 1 step further from the original rotten orange that started the initial DFS.

Once we come back from the DFS at that position, we update the value with min value between the old value at that position and the new distance/time.

So basically we are comparing if there is a shorter path from another rotten orange to this fresh orange.

And that's it. Once we go through the whole grid, we have updated the fresh oranges with values that represent the distance/time to rotten the oranges. We just need to pick the maximum of all of those times to get the answer.

Just one thing, we have to be careful to remove the offset that we added, as that offset was just added to avoid the semantics of the values in the grid.

Here is the full solution:

    private static final int FRESH = 1;
    private static final int ROTTEN = 2;
    public static final int TIME_OFFSET = 3;
    public static final int CANNOT_BE_ROTTEN = -1;

    public int orangesRotting(int[][] grid) {
        setMinTimeToRotten(grid);
        int maxTime = getMaxTimeToRotten(grid);
        if (maxTime == CANNOT_BE_ROTTEN) return CANNOT_BE_ROTTEN;
        return Math.max(0, maxTime - TIME_OFFSET);
    }

    private void setMinTimeToRotten(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == ROTTEN) {
                    dfsInAllDirections(grid, i, j, 1 + TIME_OFFSET);
                }
            }
        }
    }

    private int getMaxTimeToRotten(int[][] grid) {
        int maxTime = 0;
        for (int[] rows : grid) {
            for (int value : rows) {
                if (value == FRESH) return CANNOT_BE_ROTTEN;
                maxTime = Math.max(value, maxTime);
            }
        }
        return maxTime;
    }

    private void dfsInAllDirections(int[][] grid, int i, int j, int time) {
        dfs(grid, i + 1, j, time);
        dfs(grid, i - 1, j, time);
        dfs(grid, i, j + 1, time);
        dfs(grid, i, j - 1, time);
    }

    private void dfs(int[][] grid, int i, int j, int time) {
        if (!isValid(grid, i, j) || !isFresh(grid[i][j])) return;
        int originalOrangeValue = grid[i][j];
        grid[i][j] = -1;
        dfsInAllDirections(grid, i, j, time + 1);
        grid[i][j] = getMinTimeToRotten(time, originalOrangeValue);
    }

    private int getMinTimeToRotten(int time, int originalOrange) {
        return originalOrange == FRESH
                ? time
                : Math.min(originalOrange, time);
    }

    private boolean isFresh(int orange) {
        return orange == FRESH || orange > ROTTEN;
    }

    private boolean isValid(int[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[i].length;
    }

Complexity

Well this is where it gets complicated. I am not sure about this analysis, so please feel free to comment if you have a better way to understand the complexity.

The key points are:

For each rotten orange, you have to calculate the distance to all reachable fresh oranges.
For simplicity let's think of a square matrix: n = m*m
n : total size of the grid
The worst case would be when we have n/2 rotten oranges and n/2 fresh oranges. Together they fill the whole grid.
This means that we would have the following:

n/2 * n/2 = 1/4 * n^2

This means: For each rotten orange(n/2) we have to calculate the distance to all fresh orange(n/2).

This would give a time complexity:

Time: O(n^2) :
Space: O(1), we are reusing the same grid and no other data structures are required.

Final comments:

I am still thinking about the complexity of the BFS, which seems that should be faster, but the submission in only 82%.

However, my DFS solution is 100%! Not sure if my complexity analysis is correct, and what/how the complexity of the BFS is.

As always try to think of different solutions. I haven't seen anyone using DFS, so I thought I would share my solution :)

Leetcode: 520. Detect Capital

Marcelo Surriabre — Sun, 02 Aug 2020 20:07:42 +0000

Introduction

Problem statement

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like "
All letters in this word are not capitals, like "leetcode".
Only the first letter in this word is capital, like "Google".

Otherwise, we define that this word doesn't use capitals in a right way.

Solution

This is quite an simple yet interesting problem. You can check the available solutions at leetcode. Here I am going to show another solution using a different approach.

First try

At first, after reading the problem statement and seeing the examples, it is easy to see that all the characters after the first one must be equal, the only problem is checking if the first character is Uppercase or Lowercase, and then, based on that information, check for the rest of the string.

That is to say:

If the string starts with an Uppercase, then either the rest of the string must also be Uppercase, or the rest of the string must in Lowercase.
If the string starts with a Lowercase, then the rest must be Lowercase as well.

That seems simple enough, and it should probably be done in one pass over the whole string, given a linear time complexity O(n).

Given this situation I was thinking in a general solution that would do one pass over the string and check some condition based on the first character.

This approach can get a bit confusing in the case the first letter is Uppercase (point number 1 mentioned above), as you would also need to check the second character to see if you need to check for all other characters to be Uppercase or lowercase.

At this point the solution may seem quite easy, but would require doing an if-else statement, with for loops, each with a similar code, but changing the conditional inside the for loop.

After some time thinking about possible solutions for this problem I came up with a not so obvious and interesting solution using some logic based on the observations of the examples.

The main idea

Instead of looking at the beginning of the string, how about looking at the end of it. The possible solutions are much simpler:

If the last character is Uppercase, then the whole String must be Uppercase.
If the last character is Lowercase, then the the whole string(skipping the first index) must be Lowercase.

We can skip the first character, now it doesn't matter at all!(well, for the most part). Because the last character actually tells us more about the string than the first character. As I mentioned before, the first character may be Uppercase or Lowercase, but the rest MUST be the same. So we just check for the case for the last character and then check for the same case for the rest of the string starting at index 1.

However we must consider one edge case, what if we have this string:

"aBCDEF"

The last character is Uppercase, and the rest of the string starting at index 1 is also Uppercase. That would be true according the previous logic. However, the result should be false, as the first character is not Uppercase. We can simply check for this edge case and that's it.

Explanation and Code

First, we check for the case of the last character. Let's say it is Uppercase:

"ABCEDFG" -> Last character "G" is Uppercase.

Then we check that all the other characters in the string starting at index 1 must be Uppercase.

The same with Lowercase. For example:

"abcdefg" -> Last character "g" is Lowercase

The logic for both cases is the same:

if Uppercase, then all characters starting at index 1 must be Uppercase.
if Lowercase, then all characters starting at index 1 must be Lowercase.

Because we have a binary decision here, we can use some propositional logic :)

Both sides of the conditional expression must be the same, otherwise we return false. That is exactly what the Exclusive or truth table provides.

So basically we can use the xor operator in Java "^" as the condition operator inside the for loop.

Finally, even before all of this we must check for the edge case. So if the last character is Lowercase and the first character is Uppercase, just return false.

The code is the following:

   public boolean detectCapitalUse(String word) {
        boolean hasToBeUppercase = Character.isUpperCase(word.charAt(word.length() - 1));
        if(hasToBeUppercase && Character.isLowerCase(word.charAt(0))) return false;
        for (int i = 1; i < word.length(); i++) {
           if(hasToBeUppercase ^ Character.isUpperCase(word.charAt(i))) return false;
        }
        return true;
    }

Always give proper names to your variables, that can make a big impact in the readability of your code.

The code is quite simple, and we just need to loop once through the characters in the string. As soon as the "xor" boolean expression is true for any string in the string, we return false. Otherwise the whole string complies with the constraints and we return true.

Complexity

Time: O(n), we only loop once through the string.
Space: O(1), we are only creating a boolean variable, which is independent of the size of the input.

Final comments:

Sometimes the solution can be more simple if we look at the problems from a different perspective. It is often the case in coding problems that it is easier to start from the "end" of the data structure (arrays, strings, lists). This was one of those cases.

Pay close attention to the examples and constraints of the problem. If possible, think of your own examples, and then given the information, try to observe some common patterns or properties that can give you more information about the problem.

Always try to think about different approaches. Try to generalize your solution so you don't repeat your code. For instance, I don't like the solution of Leetcode (approach 1), as it uses an if-else statement, both doing practically the same, except for the condition inside the for loop, which can be generalized as I demonstrated here.

Leetcode: 665. Non-decreasing Array

Marcelo Surriabre — Fri, 24 Jul 2020 22:18:28 +0000

Introduction

Problem statement

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Summary: You have a method that returns true is the array, passed as input, can become increasing (non-decreasing), meaning the values in the array are equal or greater that the previous element in the array. You can change at most one element in the array to make this happen.

Solution

The solutions provided by leetcode are quite confusing (and the code only in python). And the optimal solution seems more complicated than it is.

First Solution

The main idea

Go through the array, if there is an element that violates the constraint (increasing), then change/mark it. Keep going through the array, if another violations occurs, then return false as we cannot change more than once. If there hasn't been any violation or we changed at most once then return true.

Explanation and Code

An increasing array should be something like this:

[1,2,2,3,4,5,5]

Every element in the array: array[i], is less than or equal than the next element: array[i+1].

array[i] <= array[i+1]

So the input array, could potentially violate this constraint at some point:

[...2,8,5,...]

In the example above, which represents an array, at some point, one of the elements is not greater or equal than the next. In this case:

8 is not greater than or equal to 2

So just do as the problem says, change it in order to fix it!

We need to change some element so that the constraints are not violated. Now the question is, what to change, which value?

The key thing here is to remember that we always need to modify the array to a state that is according to the constraints, in this case we must make the elements of the array increasing.

So we have the following constraints about the state of the array at any index:

Any element before index "i": array[i-1], should be less than or equal to the element at index "i": array[i]
Any element after index "i": array[i+1], should be greater than or equal to the element at index "i": array[i]

We need these 2 constraints to guarantee that the array values are increasing and we need to maintain them.

Whatever is the change we choose to make, those 2 constraints must be maintained after the change.

At this point, the solution is easy if we consider the "combinations" we could have with both previous and next elements in the array, in reference to the index where the constraints are not maintained.

If the previous element in the array is greater than the next element, then we need to change the next element to the value of the current element:

array[i+1] = array[i]

Example:

[...8,10,5,...] // Not in increasing order, 10 > 5

array[i] = 10
array[i-1] > array[i+1]
8 > 5

So to fix we change array[i+1] to array[i]:

[...8,10,10,...]

This is the only way we will guarantee that we maintain the increasing order and comply with the constraints.

If the previous element in the array is less than the next element, we need to change the current element to the value of the next element:

array[i] = array[i+1]

[...4,9,7...] // Not in increasing order, 9 > 7

array[i] = 9
array[i-1] < array[i+1]
4 > 7

So to fix it we change array[i] to array[i+1]:

[...4,7,7,...]

This is the only way we will guarantee that we maintain the increasing order and comply with the constraints.

Note that we could also change array[i+1] to 9, but that could mess up the next elements after array[i+1].

The code is the following:

    public boolean checkPossibility(int[] nums) {
        boolean changed = false;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (changed) return false;
                if (i != 0 && nums[i - 1] > nums[i + 1]) {
                    nums[i + 1] = nums[i];
                }
                changed = true;
            }
        }
        return true;
    }

In the actual code we don't really need to change for the second case, where array[i-1] < array[i+1], because we are gonna keep checking the array with array[i+i], and because that value is not changed at all, we can ignore the "actual" change which occurs at array[i].

What we always need, is to have a boolean variable, that indicates if we previously did a change on the array. So in the case we did and the variable "changed" is true, then we can no longer do any other change and we should return false if another change is required.

The code is simple and clear. One disadvantage of this approach is that we are mutating the input, which is not good if we try to think in terms of pure functions.

Complexity

Time: O(n), we only loop once through the whole array
Space: O(1), we are only creating a new variable: "changed", however this does not depend on the size of the input, hence, we have constant space complexity.

Second solution

If you really don't want to modify the input, there are ways to avoid this. One of which is the following:

   public boolean checkPossibility2(int[] nums) {
        boolean changed = false;
        int currentValue = nums[0];
        for (int i = 0; i < nums.length - 1; i++) {
            if (currentValue > nums[i + 1]) {
                if (changed) return false;
                if (i != 0 && nums[i - 1] > nums[i + 1]) {
                    currentValue = nums[i];
                } else {
                    currentValue = nums[i + 1];
                }
                changed = true;
            } else {
                currentValue = nums[i + 1];
            }
        }
        return true;
    }

The idea is the same, but we need to have another variable: "currentValue" to hold the currentValue in case it changes.

Another solution:

You could also do the same as approach 1 and change the original array, but save the changed value and index, so at the end of the for loop you replace back the original value. While this solution does not seem to change the original input, it could lead to problems if you have concurrent access to the method, as the input can be different at some point in time. Obviously this is not an issue for this problem, but it is something to consider when working in concurrent applications, and always good to remember.