DEV Community: Avin Sharma

Settings - I

Avin Sharma — Fri, 05 Jun 2020 00:00:00 +0000

In the previous post we created a menu with a single element with the title “Settings”. In this post we are going to create a settings screen and connect it to the settings option in the menu. You can get the code for everything we have done till now here

Add Preferences Dependency

Add the following to the app level build.gradle and then sync it.

implementation 'androidx.preference:preference:1.1.1'

Create a Settings Activity

We want to create an Activity that launches when the settings option is clicked. The settings activity will be the child of MainActivity, we do this so that when we press back from the settings activity we go back to the MainActivity.

Let’s create an Empty Activity and name it SettingsActivity, change from EmptyActivity to SettingsActivity.

We will add a fragment to the xml of this activity later when we have our fragment ready.

Create Settings Preferences XML

The XML we are going to create now controls how our settings looks and all the values in it. This xml file has to be in a resource directory called xml (res/xml/settings_pref.xml). So let’s create a resource directory called xml and add an xml file called settings_pref.xml.

Here we are creating a ListPreference because we want to select a single option out of many there are other preferences like SwitchPreference, MultiSelectListPreference, etc. This link might be useful if you want to find out about other preferences.

<?xml version="1.0" encoding="utf-8"?>
<PreferenceScreen
    xmlns:android="http://schemas.android.com/apk/res/android">

    <ListPreference
        android:title="Sort By"
        android:key="sort-by"
        android:defaultValue="@string/pref_sort_by_key_default"
        android:entries="@array/pref_repo_sort_by_option_labels"
        android:entryValues="@array/pref_repo_sort_by_option_values"
        android:summary="@string/pref_sort_by_summary"/>

</PreferenceScreen>

I have created all the strings in res/values/strings.xml and created another file res/values/arrays.xml where I created the two arrays I am using for entries and entryValues. This is what my arrays look like:

<?xml version="1.0" encoding="utf-8"?>
<resources>
    <array name="pref_repo_sort_by_option_labels">
        <item>@string/pref_sort_by_label_default</item>
        <item>@string/pref_sort_by_label_stars</item>
        <item>@string/pref_sort_by_label_forks</item>
        <item>@string/pref_sort_by_label_updated</item>
        <item>@string/pref_sort_by_label_help_wanted_issues</item>
    </array>

    <array name="pref_repo_sort_by_option_values">
        <item>@string/pref_sort_by_key_default</item>
        <item>@string/pref_sort_by_key_stars</item>
        <item>@string/pref_sort_by_key_forks</item>
        <item>@string/pref_sort_by_key_updated</item>
        <item>@string/pref_sort_by_key_help_wanted_issues</item>
    </array>
</resources>

and the strings like so:

    <!-- Sort By List Preference Strings -->
    <string name="pref_sort_by_summary">Select which parameter to sort the results of the query by</string>
    <string name="pref_sort_by_key" translatable="false">sort-by</string>
    <string name="pref_sort_by_label">Sort By</string>

    <string name="pref_sort_by_label_default">Default</string>
    <string name="pref_sort_by_label_stars">Stars</string>
    <string name="pref_sort_by_label_forks">Forks</string>
    <string name="pref_sort_by_label_updated">Recently Updated</string>
    <string name="pref_sort_by_label_help_wanted_issues">Help Wanted Issues</string>

    <string name="pref_sort_by_key_default">default</string>
    <string name="pref_sort_by_key_stars">stars</string>
    <string name="pref_sort_by_key_forks">forks</string>
    <string name="pref_sort_by_key_updated">updated</string>
    <string name="pref_sort_by_key_help_wanted_issues">help-wanted-issues</string>

Entries is what will be shown in the settings and entryValues is their corresponding keys that we will use in the code later. One important thing to note here is that the order of the items in both the arrays should be the same.

Create SettingsFragment

Create a new class in the same directory as the MainActivity called SettingsFragment which extends PreferenceFragmentCompat

package com.avinsharma.githubrepositorysearch;

import android.os.Bundle;

import androidx.preference.PreferenceFragmentCompat;

public class SettingsFragment extends PreferenceFragmentCompat {
    @Override
    public void onCreatePreferences(Bundle savedInstanceState, String rootKey) {
        addPreferencesFromResource(R.xml.settings_pref);
    }
}

Add the newly created Fragment to SettingsActivity XML

In the activity_settings.xml

<?xml version="1.0" encoding="utf-8"?>
<fragment
    xmlns:android="http://schemas.android.com/apk/res/android"
    android:name="com.avinsharma.githubrepositorysearch.SettingsFragment"
    android:layout_width="match_parent"
    android:layout_height="match_parent"/>

Launch SettingsActivity on settings menu option click

Now instead of a Toast we want to launch the SettingsActivity from the MainActivity when settings menu option is clicked.

    @Override
    public boolean onOptionsItemSelected(@NonNull MenuItem item) {
        switch (item.getItemId()) {
            case R.id.settings_menu_option:
                Intent intent = new Intent(this, SettingsActivity.class);
                startActivity(intent);
                return true;
            default:
                return super.onOptionsItemSelected(item);
        }
    }

Finally make MainActivity the parent of SettingsActivity in the Manifest

We want SettingsActivity to be the child Activity of MainActivity so that android gives us a back button on the UI and also know where to go back to.

In the manifest we add parentActivityName to the SettingsActivity:

<activity android:name=".SettingsActivity"
            android:parentActivityName=".MainActivity"></activity>

Conclusion

To summarize do the following steps to create simple settings

Add Dependency
Create a Settings Activity
Create Settings Preferences XML
Create SettingsFragment
Add the newly created Fragment to SettingsActivity XML
Launch SettingsActivity on settings menu option click
Finally make MainActivity the parent of SettingsActivity in the Manifest

This is what our settings looks like right now:

We have created settings for our app where we offer different ways to sort the github queries but nothing happens when we choose a different option. In the next post we will explore how to detect changes in settings and how to get the current selected settings using SharedPreferences.

You can find the code for everything done up till now here.

As always if you find any errors, have feedback or just want to say hi please don’t hesitate to leave a comment below.

<?xml version="1.0" encoding="utf-8"?>
<menu 
    xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto">
    <item
        android:id="@+id/settings_menu_option"
        android:title="@string/settings_menu_option_title"
        app:showAsAction="never"/>

</menu>

We have a menu tag and everything inside this tag is displayed in the menu. We can add items as we did above or add another menu (a sub menu).

There are a lot of attributes that can be added here but in most of the cases we wouldneed just the three we used above: id, title, showAsAction.

Id of the items are used later to determine which item was clicked in the menu, title is the text that we see on the item when the menu is displayed and finally showAsAction determines if the item stays in the overflow(the three dots we click to see the menu, usually on the top right) or is shown on the app bar.

Inflate menu in the activity

Now that we have our layout XML we can now inflate it to display in the MainActivity. Just override onCreateOptionsMenu, inflate the menu and return true

    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        MenuInflater inflater = getMenuInflater();
        inflater.inflate(R.menu.main_menu, menu);
        return true;
    }

Now the menu should show up but nothing should happen when you click on the items.

Handle clicks in the activity

To handle click in the same activity, in our case the MainActivity override onOptionsItemSelected identify which item is being clicked and handle the clicks accordingly.

    @Override
    public boolean onOptionsItemSelected(@NonNull MenuItem item) {
        switch (item.getItemId()) {
            case R.id.settings_menu_option:
                Toast.makeText(this, "Settings option clicked!", Toast.LENGTH_LONG).show();
                return true;
            default:
                return super.onOptionsItemSelected(item);
        }
    }

With this clicking on settings should display a toast.

A Menu added

We have a menu now, but all we do is display a Toast. In the next post we will explore how to create a settings screen using preferenceFragment and saving the settings using sharedPreferences.

Intents

Avin Sharma — Sat, 30 May 2020 00:00:00 +0000

What are intents?

The android documentation describes intents very well:

An Intent object carries information that the Android system uses to determine which component to start (such as the exact component name or component category that should receive the intent), plus information that the recipient component uses in order to properly perform the action (such as the action to take and the data to act upon).

Types of Intents

Explicit
Implicit

Let’s just dive into code samples, I think looking at some code will make a lot of sense.

Explicit Intent

In the app we have been building if I want to start a new activity(say DetailsActivity.class) when I click a list item this is how we would do it

Intent intent = new Intent(this, DetailsActivity.class);
intent.putExtra(...); // Send some details to the new activity (OPTIONAL)
startActivity(intent);

It is called explicit Intent because we are explicitly telling the intent which component to start. We could start activities in our all like we did in the example above or in some other app, but that app should exist in the user’s device. Basically when we know exactly what we want to start we use explicit intent.

Implicit Intent

This is the other part on intents. We use implicit intents when we don’t know or don’t care which app or component is used. Some example would be when we want to open a location on a map or when we want to click a picture we don’t care which app ends up handling our request(from a developer’s perspective that is, if there are multiple apps that can handle our request the user is presented with a selection of choices).

An example of implicit intent to set an alarm.

public void createAlarm(String message, int hour, int minutes) {
    Intent intent = new Intent(AlarmClock.ACTION_SET_ALARM)
            .putExtra(AlarmClock.EXTRA_MESSAGE, message)
            .putExtra(AlarmClock.EXTRA_HOUR, hour)
            .putExtra(AlarmClock.EXTRA_MINUTES, minutes);
    if (intent.resolveActivity(getPackageManager()) != null) {
        startActivity(intent);
    }
}

Here is a really helpful link which has most of the common intents.

I believe this is enough to get started, there are other things that the intents are used to start like broadcasts and services. We might want to research more when we are doing something more specific but preemptively learning about all the kinds of intents is not particularly helpful, we can always refer back to the documentation when needed.

This was a short one but was an important pit stop since we are going to use intents soon to start details activity on list item click and to navigate to preferences.

I think I want to create a menu next through which we can go to the preferences and then create preferences so that we can change query parameters. Then explore modelview and livedata to handle configuration changes like screen rotations.

As always if you find any errors, have feedback, or just want to say hi please don’t hesitate to leave a comment below.

RecyclerView - II, adding onClick to list items

Avin Sharma — Fri, 29 May 2020 00:00:00 +0000

We have a RecyclerView that displays a list of Github Repositories, but we might want to display more details of each of the repositories in the future, so we want each of the list items to react to our clicks. Let's see how we can do that. You can get the code for everything we have done up till now, here to follow along.

Overview

Setting up onClick in a RecyclerView is not as straightforward as setting up onClick on a button, but once you create it yourself it makes a lot more sense. What we are doing here is calling interface’s function in the ViewHolder’s onClick and defining what this function will do in the activity by implementing the interface in the activity.

Create an interface ListItemClickListener with an onClickListItem(can be named anything) method.
Create a ListItemClickListener member variable of the adapter called mOnClickListener.
Add a ListItemClickListener as a parameter to the constructor and store it in mOnClickListener
Implement View.OnClickListener in the ViewHolder class and add itemView.setOnClickListener(this); in the ViewHolder constructor.
Override onClick in the ViewHolder class and get the position being clicked using getAdapterPosition() and use the position to call mOnClickListener.onListItemClick(position), the function in the interface we created.
In the activity where the RecyclerView was created implement the ListItemClickListener interface.
Fix the adapter initialization since we changed the adapter constructor in the activity onCreate.
Override onClickListItem(int position) and use the position of the item clicked to do something with it. Since the data to the RecyclerView is usually passed from the same activity, we can use the position to get data of the item that is clicked.

In the Adapter

In the adapter class we add the following

    interface ListItemClickListener{
        void onListItemClick(int position);
    }

and create a member variable of type ListItemClickListener

    final private ListItemClickListener mOnClickListener;

and the change the constructor of the adapter to accept a parameter of type ListItemClickListener, in our case we create one since we did not have one.

    public RepositoryAdapter(ListItemClickListener onClickListener){
        this.mOnClickListener = onClickListener;
    }

implement onClickListener in the ViewHolder class

    public class RepositoryAdapterViewHolder extends RecyclerView.ViewHolder implements View.OnClickListener

add itemView.setOnClickListener(this); to the constructor

    public RepositoryAdapterViewHolder(@NonNull View itemView) {
        super(itemView);
        ...
        ...
        itemView.setOnClickListener(this);
    }

and then override onClick in the ViewHolder, since we implement View.OnClickListener

        @Override
        public void onClick(View v) {
            int position = getAdapterPosition();
            mOnClickListener.onListItemClick(position);
        }

In the Activity

Now we just need to implement the interface we just created in the activity and fix the RecyclerView Adapter initialization

public class MainActivity extends AppCompatActivity implements RepositoryAdapter.ListItemClickListener

then fix adapter initialization:

    mRepositoryAdapter = new RepositoryAdapter(this);

and the finally override onListItemClick

    @Override
    public void onListItemClick(int position) {
        Toast.makeText(this, mRepos[position].getName(), Toast.LENGTH_SHORT).show();
    }

List Items are now clickable!

When we click on an item a Toast with the name of the repository is displayed. We could start a new activity with details of the activity, but to start an activity we need to create an intent. Intents can be used to start an activity in your own app or in some other app. In the next post let’s explore Intents.

You can find the code for everything we have done in this post here.

Hopefully, you feel more comfortable using RecyclerView. If you find any errors, have feedback, or just want to say hi please don’t hesitate to leave a comment below.

RecyclerView - I

Avin Sharma — Mon, 25 May 2020 00:00:00 +0000

Up till now we have created an app that can query the GitHub API, parse the JSON, and display names and descriptions in a single TextView. You can get the code here to follow along.

Why are we using RecyclerView and what problem does it solve for us?

It gives us the ability to use complex layout for items in the list, there is only so you can do with appending in a TextView.
It allows us to display our list vertically, horizontally, in a grid, or a custom layout.
It does a lot of optimizations, but mainly it recycles views in the list as the name suggests. For example if we have 100 items, only 10 list items are used and displayed out of which 7 are being displayed and 3 are being used for smooth scrolling. The idea here is to not generate views for all 100 items and only generate enough to cover the screen and a few extra and keep using them over and over again.

Components of a RecyclerView

A high-level overview of how everything is connected

RecyclerView: The primary view where the list is displayed
Adapter: Provides RecyclerView with new views(list items) when needed and binds data to the new and recycled views. The views are sent in a ViewHolder. The two of them can be considered sort of a single unit.
ViewHolder: Contains reference to the view objects of the item. This caches view objects which allow us to reuse/recycle views. When we scroll a list and an item is scrolled out of the screen, the views in that list item are bound to new data and used as a new list item, this reduces findViewById calls required for generating new views.
Data Source: We could have a data source JSON/Database/Anything which is used to get data and populate our list items in our RecyclerView, the adapter pulls in data from here and binds it to the views.
Layout Manager: Manages the layout of the list items. RecyclerView prepares the list items and the layout manager manages how these items are arranged(Linear, Grid, Staggered Grid, Custom).

How do we create a RecyclerView

This is generally what the sequence would be:

Add RecyclerView dependency.
Add RecyclerView to the layout.
Create a layout for list items.
Create Adapter and ViewHolder inside the adapter.
Create a Layout Manager, reference RecyclerView, and create a new Adapter in the code.
Connect Layout Manager and Adapter to the RecyclerView.
Connect or change the data source if needed.

Adding dependency

Add the following to your dependency section in the app level build.gradle

implementation 'com.android.support:recyclerview-v7:28.0.0'

Since there will be no more releases to the support library, android studio now prompts to migrate to androidx if we add the above dependency. I used android studio’s migration and it took care of everything and changed the dependency for me.

Another way would be to set android.useAndroidX=true and android.enableJetifier=true in gradle.properties and then add the following dependency:

implementation 'androidx.recyclerview:recyclerview:1.1.0'

Adding RecyclerView to the Layout

We start by removing the ScrollView and the TextView inside in the activity_main.xml and replace it by RecyclerView

    <androidx.recyclerview.widget.RecyclerView
        android:id="@+id/rv_repo_list"
        android:layout_width="match_parent"
        android:layout_height="match_parent"/>

Creating Layout for List Items

This is the layout for each item in the list. I use LinearLayout and TextView to keep things simple. We need to display the 6 things that we store in a Repository item, so in the layout we have 6 TextViews with id’s so that we can change their text when needed. Let’s create a repository_list_item.xml in the layout folder (res -> layout -> repository_list_item.xml) and create a layout.

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout
    xmlns:android="http://schemas.android.com/apk/res/android"
    android:orientation="vertical"
    android:layout_width="match_parent"
    android:layout_height="wrap_content"
    android:layout_marginHorizontal="8dp">

    <TextView
        android:id="@+id/tv_repo_name"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:textStyle="bold"/>

    <TextView
        android:id="@+id/tv_repo_description"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"/>

    <LinearLayout
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:orientation="horizontal">

        <TextView
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:text="Stars:"/>

        <TextView
            android:id="@+id/tv_star_count"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"/>

    </LinearLayout>

    <LinearLayout
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:orientation="horizontal">

        <TextView
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:text="Updated on: "/>

        <TextView
            android:id="@+id/tv_updated_at"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"/>

    </LinearLayout>

    <TextView
        android:id="@+id/tv_language"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:textColor="@color/colorPrimary"/>

    <TextView
        android:id="@+id/tv_license"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:textColor="@color/colorAccent"/>

    <View
        android:layout_width="wrap_content"
        android:layout_height="1dp"
        android:background="#dadada"
        android:layout_marginVertical="8dp"/>

</LinearLayout>

Creating a RecyclerView Adapter and ViewHolder

The adapter’s job is to provide RecyclerView with new views when needed and bind data. Now the views are provided to the RecyclerView in a ViewHolder. The ViewHolder calls findViewById to find and cache the views so that we don’t call findViewById for each data point.

My strategy is to create the ViewHolder first after we create the skeleton for our Adapter and then move on to filling the rest of the required functions in the adapter.

public class RepositoryAdapter extends RecyclerView.Adapter<RepositoryAdapter.RepositoryAdapterViewHolder> {

    private Repository[] mAllRepositories;

    public static class RepositoryAdapterViewHolder extends RecyclerView.ViewHolder{
        // Connects to TextViews in repository_list_items.xml
        public final TextView mRepositoryName;
        public final TextView mRepositoryDescription;
        public final TextView mRepositoryStarCount;
        public final TextView mRepositoryLanguage;
        public final TextView mRepositoryUpdatedAt;
        public final TextView mRepositoryLicense;

        public RepositoryAdapterViewHolder(@NonNull View itemView) {
            super(itemView);
            this.mRepositoryName = itemView.findViewById(R.id.tv_repo_name);
            this.mRepositoryDescription = itemView.findViewById(R.id.tv_repo_description);
            this.mRepositoryStarCount = itemView.findViewById(R.id.tv_star_count);
            this.mRepositoryLanguage = itemView.findViewById(R.id.tv_language);
            this.mRepositoryUpdatedAt = itemView.findViewById(R.id.tv_updated_at);
            this.mRepositoryLicense = itemView.findViewById(R.id.tv_license);
        }

        private void bind(Repository repo){
            String name = repo.getName();
            String description = repo.getDescription();
            Integer stargazersCount = repo.getStargazersCount();
            String language = repo.getLanguage();
            String updatedAt = repo.getUpdatedAt();
            String license = repo.getLicense();

            mRepositoryName.setText(name);
            mRepositoryStarCount.setText(String.valueOf(stargazersCount));
            mRepositoryUpdatedAt.setText(updatedAt);

            // Since the data in these can be null we check and bind data
            // or remove the view otherwise
            bindOrHideTextView(mRepositoryDescription, description);
            bindOrHideTextView(mRepositoryLanguage, language);
            bindOrHideTextView(mRepositoryLicense, license);

        }

        private void bindOrHideTextView(TextView textView, String data){
            if (data == null){
                textView.setVisibility(View.GONE);
            }
            else{
                textView.setText(data);
                textView.setVisibility(View.VISIBLE);
            }
        }
    }
}

We then override the 3 methods onCreateViewHolder(), onBindViewHolder(), and getItemCount() required in a RecyclerView. onCreateViewHolder() is called to create new views. I experimented with this and in our case onCreateViewHolder() was called only 8 times, which means for all the other items the views were recycled.

In onBindViewHolder() we bind data to views. We can get either a new view which has no data attached to it or we could get a recycled view which has some data that we attached previously, we attach new data to the view we get. It is not required but I created a bind method in the ViewHolder to keep things clean and call it in onBindViewHolder() instead of binding data directly in onBindViewHolder().

Here I have a member variable called mAllRepositories and it is supposed to hold all the repositories. It is used in onBindViewHolder(), to bind views in the ViewHolder to data and in getItemCount() to get the count of items. Since mAllRepositories is going to be empty in the beginning, I have created the method setmAllRepositories so that we can call the method to assign data from AsyncTask after we fetch data from the Internet.

    @NonNull
    @Override
    public RepositoryAdapterViewHolder onCreateViewHolder(@NonNull ViewGroup parent, int viewType) {
        Context context = parent.getContext();
        LayoutInflater inflater = LayoutInflater.from(context);
        View view = inflater.inflate(R.layout.repository_list_item, parent, false);
        return new RepositoryAdapterViewHolder(view);
    }

    @Override
    public void onBindViewHolder(@NonNull RepositoryAdapterViewHolder holder, int position) {
        holder.bind(mAllRepositories[position]);
    }

    @Override
    public int getItemCount() {
        if (mAllRepositories == null) return 0;
        return mAllRepositories.length;
    }

    public void setmAllRepositories(Repository[] repositories){
        mAllRepositories = repositories;
        notifyDataSetChanged();
    }

This is what the full adapter class looks like with ViewHolder and all the methods.

public class RepositoryAdapter extends RecyclerView.Adapter<RepositoryAdapter.RepositoryAdapterViewHolder> {

    private Repository[] mAllRepositories;

    public static class RepositoryAdapterViewHolder extends RecyclerView.ViewHolder{
        public final TextView mRepositoryName;
        public final TextView mRepositoryDescription;
        public final TextView mRepositoryStarCount;
        public final TextView mRepositoryLanguage;
        public final TextView mRepositoryUpdatedAt;
        public final TextView mRepositoryLicense;

        public RepositoryAdapterViewHolder(@NonNull View itemView) {
            super(itemView);
            this.mRepositoryName = itemView.findViewById(R.id.tv_repo_name);
            this.mRepositoryDescription = itemView.findViewById(R.id.tv_repo_description);
            this.mRepositoryStarCount = itemView.findViewById(R.id.tv_star_count);
            this.mRepositoryLanguage = itemView.findViewById(R.id.tv_language);
            this.mRepositoryUpdatedAt = itemView.findViewById(R.id.tv_updated_at);
            this.mRepositoryLicense = itemView.findViewById(R.id.tv_license);
        }

        private void bind(Repository repo){
            String name = repo.getName();
            String description = repo.getDescription();
            Integer stargazersCount = repo.getStargazersCount();
            String language = repo.getLanguage();
            String updatedAt = repo.getUpdatedAt();
            String license = repo.getLicense();

            mRepositoryName.setText(name);
            mRepositoryStarCount.setText(String.valueOf(stargazersCount));
            mRepositoryUpdatedAt.setText(updatedAt);

            // Since the data in these can be null we check and bind data
            // or remove the view otherwise
            bindOrHideTextView(mRepositoryDescription, description);
            bindOrHideTextView(mRepositoryLanguage, language);
            bindOrHideTextView(mRepositoryLicense, license);

        }

        private void bindOrHideTextView(TextView textView, String data){
            if (data == null){
                textView.setVisibility(View.GONE);
            }
            else{
                textView.setText(data);
                textView.setVisibility(View.VISIBLE);
            }
        }
    }

    @NonNull
    @Override
    public RepositoryAdapterViewHolder onCreateViewHolder(@NonNull ViewGroup parent, int viewType) {
        Context context = parent.getContext();
        LayoutInflater inflater = LayoutInflater.from(context);
        View view = inflater.inflate(R.layout.repository_list_item, parent, false);

        return new RepositoryAdapterViewHolder(view);
    }

    @Override
    public void onBindViewHolder(@NonNull RepositoryAdapterViewHolder holder, int position) {
        holder.bind(mAllRepositories[position]);
    }

    @Override
    public int getItemCount() {
        if (mAllRepositories == null) return 0;
        return mAllRepositories.length;
    }

    public void setmAllRepositories(Repository[] repositories){
        mAllRepositories = repositories;
        notifyDataSetChanged();
    }
}

Creating and connecting Layout Manager, RecyclerView, and RepositoryAdapter in the code.

We add RecyclerView and RepositoryAdapter member variables in the MainActivity

    private RecyclerView mRepositoryRecyclerView;
    private RepositoryAdapter mRepositoryAdapter;

and then initialize both of the above variables, create a LayoutManager, and finally connect everything.

    mRepositoryRecyclerView = findViewById(R.id.rv_repo_list);
    mRepositoryAdapter = new RepositoryAdapter();

    LinearLayoutManager layoutManager = new LinearLayoutManager(this);
    layoutManager.setOrientation(RecyclerView.VERTICAL);

    mRepositoryRecyclerView.setLayoutManager(layoutManager);
    mRepositoryRecyclerView.setAdapter(mRepositoryAdapter);

Connecting data fetched from the internet to the RecyclerView

We have everything set up, but we are fetching the data in the AsyncTask, but that data is not shared with the RecyclerView. This is where the method we created earlier setmAllRepositories comes in handy. We add mRepositoryAdapter.setmAllRepositories(mRepos); in the onPostExecute and clean up code related to the TextView that we were using previously.

        @Override
        protected void onPostExecute(String s) {
            super.onPostExecute(s);
            try {
                // Get the main JSON object from the String
                JSONObject json = new JSONObject(s);

                // Get all the repos
                JSONArray repos = json.getJSONArray("items");

                mRepos = new Repository[repos.length()];

                // loop every repo and add the repo array
                for(int i = 0; i < repos.length(); i++){
                    JSONObject repo = repos.getJSONObject(i);
                    mRepos[i] = JSONUtils.parseRepositoryJSON(repo);
                }

                // Send data to the RecyclerView
                mRepositoryAdapter.setmAllRepositories(mRepos);
            }catch (JSONException e){
                e.printStackTrace();
            }

            mRepositoryRecyclerView.setVisibility(View.VISIBLE);
            mProgressBar.setVisibility(View.GONE);
        }

New Look!

And we are done! We moved from using a single TextView to using a RecyclerView. This is what our app looks like right now.

You can find the code for everything we have done in this post here.

The app looks much more organized, but we can only scroll the list right now. Let’s explore how to add click functionality to the RecyclerView list items in the next post.

Hopefully you feel more comfortable with using RecyclerView. If you find any errors, have feedback, or just want to say hi please don’t hesitate to leave a comment below.

JSON Parsing

Avin Sharma — Sat, 23 May 2020 00:00:00 +0000

If you have been following along you can keep working on what we made in the last post otherwise, you can grab the code for everything we have done till now here to follow along.

In the last post we fetched some data from Github API. We now want to parse it so that we can use it to do something meaningful. If you are unsure about what JSON is this might help.

Let’s take a look at a query to figure out what our JSON looks like and what to fetch. There are a lot of things that we could use, let's just try to display names of repos in the TextView. Displaying data in a list using a RecyclerView is a better approach than squashing everything in a single TextView, but that’s for another post.

Parsing is pretty straight forward, JSON arrays are inside square brackets [] and object in curly brackets {}. I think method names are pretty self explanatory. Here is how I am getting the names of repos from the JSON:

        @Override
        protected void onPostExecute(String s) {
            super.onPostExecute(s);
            try {
                // Get the main JSON object from the String
                JSONObject json = new JSONObject(s);

                // Get all the repos 
                JSONArray repos = json.getJSONArray("items");

                // loop every repo and add the name to the TextView
                for(int i = 0; i < repos.length(); i++){
                    JSONObject repo = repos.getJSONObject(i);
                    mSearchResultTextView.append(repo.getString("name") + "\n\n");
                }
            }catch (JSONException e){
                e.printStackTrace();
            }

            // We don't need this now since we are adding the names above
            // mSearchResultTextView.setText(s);
            mSearchResultTextView.setVisibility(View.VISIBLE);
            mProgressBar.setVisibility(View.INVISIBLE);
        }

We get the main JSON object from the string using JSONObject json = new JSONObject(s); and then we can use functions like getJSONObject, getJSONArray, getString, and so forth, on the JSON arrays and objects based on what we want to fetch.

In the JSON we get here we have the main JSON object which has an array named items and each item in the array contains repos which are JSONObjects and each of these JSONObjects contains a string which contains the name of the repo.

Now instead of displaying everything now we are displaying the repository names. This is what it looks like:

This is already looking better, but we might want to use more than just the name of the repository in the future. Creating a custom class to hold the data seems like a good idea here. We might end up changing the class or completely deleting it in the future, but that is fine we will refactor our app when the time comes.

Refactoring - Adding a new Repository Class

Let’s create a new package called model and inside it create a new class called Repository. After taking a look at what github.com, they list name, description, stars, language, updated at and license on every item when you do a search, so for now I have added these to our class and generated getter and setter methods for each one of them.

// Repository.class
package com.avinsharma.githubrepositorysearch.model;

public class Repository {
    private String name = null;
    private String description = null;
    private Integer stargazersCount = null;
    private String language = null;
    private String updatedAt = null;
    private String license = null;

    public Repository(String name, String description, Integer stargazersCount, String language, String updatedAt, String license) {
        this.name = name;
        this.description = description;
        this.stargazersCount = stargazersCount;
        this.language = language;
        this.updatedAt = updatedAt;
        this.license = license;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getDescription() {
        return description;
    }

    public void setDescription(String description) {
        this.description = description;
    }

    public Integer getStargazersCount() {
        return stargazersCount;
    }

    public void setStargazersCount(Integer stargazersCount) {
        this.stargazersCount = stargazersCount;
    }

    public String getLanguage() {
        return language;
    }

    public void setLanguage(String language) {
        this.language = language;
    }

    public String getUpdatedAt() {
        return updatedAt;
    }

    public void setUpdatedAt(String updatedAt) {
        this.updatedAt = updatedAt;
    }

    public String getLicense() {
        return license;
    }

    public void setLicense(String license) {
        this.license = license;
    }
}

Now that we have a class that stores everything that we need, we need to use it. Just to make our life easier I also added another class in utilities called JSONUtils where I parse JSON and return a new Repository item that contains all the details that we parsed.

package com.avinsharma.githubrepositorysearch.utilities;

import com.avinsharma.githubrepositorysearch.model.Repository;

import org.json.JSONException;
import org.json.JSONObject;

public class JSONUtils {
    public static Repository parseRepositoryJSON(JSONObject repo){
        Repository newRepository = null;

        try {
            String name = repo.getString("name");
            String updatedAt = repo.getString("updated_at");
            Integer stargazersCount = repo.getInt("stargazers_count");

            // These could be null
            String description = null;
            if (!repo.isNull("description")){
                description = repo.getString("description");
            }

            String language = null;
            if (!repo.isNull("language")){
                language = repo.getString("language");
            }

            String license = null;
            if (!repo.isNull("license")){
                license = repo.getJSONObject("license").getString("spdx_id");
            }

            newRepository = new Repository(name, description, stargazersCount, language, updatedAt, license);

        }catch (JSONException e){
            e.printStackTrace();
        }

        return newRepository;
    }
}

Now finally we make changes in our AsyncTask and use the class and JSON utility that we just made to display the search result.

        @Override
        protected void onPostExecute(String s) {
            super.onPostExecute(s);
            try {
                // Get the main JSON object from the String
                JSONObject json = new JSONObject(s);

                // Get all the repos
                JSONArray repos = json.getJSONArray("items");

                mRepos = new Repository[repos.length()];

                // loop every repo and add the name to the TextView
                for(int i = 0; i < repos.length(); i++){
                    JSONObject repo = repos.getJSONObject(i);
                    // Using the util we created here
                    mRepos[i] = JSONUtils.parseRepositoryJSON(repo);

                    // Adding name and description to the TextView
                    mSearchResultTextView.append(mRepos[i].getName());
                    if (mRepos[i].getDescription() != null){
                        mSearchResultTextView.append("\n" + mRepos[i].getDescription());
                    }
                    mSearchResultTextView.append("\n\n");
                }
            }catch (JSONException e){
                e.printStackTrace();
            }

            mSearchResultTextView.setVisibility(View.VISIBLE);
            mProgressBar.setVisibility(View.GONE);
        }

Although we haven’t added new functionality this class will make our life easier in the future when we generate more complex views.

This is what our app looks like right now:

You can find everything we have done in this post here.

This does not look bad but we can do better, we can use the 6 things that we parse from the JSON and display it. In the next post we will explore Recycler View. Recycler view will give us a better user interface and a better user experience, it allows us to display lists with more complex views and gives us the ability to do something when we click an item.

Async Task

Avin Sharma — Wed, 20 May 2020 00:00:00 +0000

AsyncTask is used to run tasks that might take some time on other thread so that the UI thread is not blocked and the UI keeps running smoothly while the task keeps running in the background.

AsyncTask is now deprecated, but I do believe it is going to be supported for a while. The alternatives are to use the standard java.util.concurrent or Kotlin concurrency utilities instead.

Before we get started with AsyncTask I want to add an OnClickListener to the Search Button so that we can respond to clicks. You can find more here. Right now we are going to create a toast that is going to display our search term.

// In onCreate after we did our findViewById's.

        mSearchButton.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                // Do something when the search button is clicked.
                Context context = v.getContext();
                Toast.makeText(context, mSearchQueryEditText.getText(), Toast.LENGTH_LONG).show();

                // TODO: Query Github API
            }
        });

This is what it looks like

Creating an AsyncTask

So AsyncTask has 4 steps:

onPreExecute() : invoked on the UI thread
doInBackground(Params…): invoked on the background threads
onProgressUpdate(Progress …): invoked on the UI thread
onPostExecute(Result): invoked on the UI thread

As the names suggest onPreExecute is invoked before doInBackground, anything you want to do before running the task goes here. Then we have doInBackground, this is where the task runs, we could also call publishProgress which sends progress updates to onProgressUpdate, it can be used to update things like progress bars or percentages. onPostExecute is where we get the result of our task.

So let's build a simple AsyncTask for our app.

// This would be outside onCreate since we are creating a new class

    private class QueryGithubAPITask extends AsyncTask<URL, Void, String>{
        @Override
        protected String doInBackground(URL... urls) {
            try {
                return NetworkUtils.getResponseFromHttpUrl(urls[0]);
            }catch (IOException e){
                e.printStackTrace();
            }
            return null;
        }

        @Override
        protected void onPostExecute(String s) {
            super.onPostExecute(s);
            mSearchResultTextView.setText(s);
        }
    }

private class QueryGithubAPITask extends AsyncTask<URL, Void, String>

We specify the type of parameters the three functions(in the order doInBackground, onProgressUpdate, onPostExecute) take at the very top, since we are not using onProgressUpdate we put Void.

        @Override
        protected String doInBackground(URL... urls) {
            try {
                return NetworkUtils.getResponseFromHttpUrl(urls[0]);
            }catch (IOException e){
                e.printStackTrace();
            }
            return null;
        }

Here all we are doing is to get a url and then pass it into a function that we previously created in our network utils in the doInBackground functions and then using the result we get and pass that on to onPostExecute.

        @Override
        protected void onPostExecute(String s) {
            super.onPostExecute(s);
            mSearchResultTextView.setText(s);
        }
    }

Since doInBackground returns a String onPostExecute accepts a String as its argument. We use the result from the doInBackground, in our case a String and set it as text in one of the TextViews.

Using the AsyncTask

Now that we have our AsyncTask setup we want to use it when we press the search button. This is pretty straight forward, we change the search buttons onClickListener to check if we have an empty search bar, and if we have a search term we search it by executing our AsyncTask.

        mSearchButton.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                String githubSearchQuery = mSearchQueryEditText.getText().toString();

                // Making sure our search bar(EditText) isn't empty
                if(githubSearchQuery.equals("")){
                    Context context = v.getContext();
                    Toast.makeText(context, "Please enter a search term.", Toast.LENGTH_SHORT).show();
                }else{
                    // Building the url with the search term
                    URL url = NetworkUtils.buildUrl(githubSearchQuery);

                    // Calling our AsyncTask
                    new QueryGithubAPITask().execute(url);
                }
            }
        });

Let's try and search for something to see if our app works

A good exercise would be to try and add a progress bar so that when we are fetching JSON we show the progress bar and when we are done fetching we hide the progress bar and show our edit text.

So the app works, but all we see is a wall of text with lots of JSON. A good idea would be to parse the JSON and display only the names of repos. Let’s explore how we could do that in the next post.

You can find the code here.

Introduction and Setup

Avin Sharma — Tue, 19 May 2020 00:00:00 +0000

Android Basics will be a series of topics that are essential for Android Development. We will go through Async Task, JSON parsing, Recycler View, Intents, Fragments, Android Lifecycle, Content Providers, and a lot more. We will learn about all the topics by implementing them in the Github Repository Search App. I do assume you know what XML is and how to reference the XML objects in Java.

The reason we are using the Github repo search API is that it does not require you to get an API key and is pretty straight forward to use.

Let's start by creating a new project with an empty activity.

Accessing the Internet

Add the following dependency in your app level build.gradle and then sync it. I am using OkHttp for the network queries.

implementation("com.squareup.okhttp3:okhttp:4.7.1")

Now let's create network utilities so that we can build and query the url. We create a separate package called utilities and add classes like NetworkUtils so that they can be used everywhere else in the app.

Create a new package called utilities and in that package/folder create a new class and name it NetworkUtils.

Add the following code to it we will use this later to get results of our GitHub search query.

package com.avinsharma.githubrepositorysearch.utilities;

import android.net.Uri;

import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;

import okhttp3.OkHttpClient;
import okhttp3.Request;
import okhttp3.Response;

public class NetworkUtils {
    private static final OkHttpClient client = new OkHttpClient();

    final static String GITHUB_BASE_URL = "https://api.github.com/search/repositories";
    final static String PARAM_QUERY = "q";

    /*
     * The sort field. One of stars, forks, or updated.
     * Default: results are sorted by best match if no field is specified.
     */
    final static String PARAM_SORT = "sort";
    final static String sortBy = "stars";

    /**
     * Builds the URL used to query GitHub.
     *
     * @param githubSearchQuery The keyword that will be queried for.
     * @return The URL to use to query the GitHub server.
     */
    public static URL buildUrl(String githubSearchQuery) {
        Uri builtUri = Uri.parse(GITHUB_BASE_URL).buildUpon()
                .appendQueryParameter(PARAM_QUERY, githubSearchQuery)
                .appendQueryParameter(PARAM_SORT, sortBy)
                .build();

        URL url = null;
        try {
            url = new URL(builtUri.toString());
        } catch (MalformedURLException e) {
            e.printStackTrace();
        }

        return url;
    }

    /**
     * This method returns the entire result from the HTTP response.
     *
     * @param url The URL to fetch the HTTP response from.
     * @return The contents of the HTTP response.
     * @throws IOException Related to network and stream reading
     */
    public static String getResponseFromHttpUrl(URL url) throws IOException {
        Request request = new Request.Builder()
                .url(url)
                .build();

        try (Response response = client.newCall(request).execute()) {
            return response.body().string();
        }
    }
}

Since we are accessing the Internet we need to have permission to do so. So we add the permission in the manifest.xml below the manifest opening tag.

<!--Permission to access internet-->
<uses-permission android:name="android.permission.INTERNET"/>

Layout for the app

Right now we are trying to search for a repo and get some JSON back as the result of a query. So we are going to keep it simple and build a layout that allows us to search and see the result of our search.

Add the following to your res -> layout -> activity_main.xml:

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout
    xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    tools:context=".MainActivity"
    android:orientation="vertical">

    <EditText
        android:id="@+id/et_search_bar"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:hint="Search for repos..."/>

    <Button
        android:id="@+id/button_search"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:padding="16dp"
        android:text="Search"
        android:layout_gravity="center"/>

    <!-- To scroll if the result is longer than our screen -->
    <ScrollView
        android:layout_width="wrap_content"
        android:layout_height="wrap_content">

        <TextView
            android:id="@+id/tv_search_result"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"/>

    </ScrollView>

</LinearLayout>

Connecting layout to code

We first create views in our MainActivity.java and then initialize them in onCreate finding them by their id.

public class MainActivity extends AppCompatActivity {

    private EditText mSearchQueryEditText;
    private Button mSearchButton;
    private TextView mSearchResultTextView;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        mSearchQueryEditText = findViewById(R.id.et_search_bar);
        mSearchButton = findViewById(R.id.button_search);
        mSearchResultTextView = findViewById(R.id.tv_search_result);
    }
}

Now that we have our layout and views setup, we are ready to tackle the next AsyncTask. AsyncTasks are used to run tasks off of the main UI thread. Since fetching data from the internet may take some time we cannot do it on the main UI thread, we use AsyncTask instead.

Right now our app looks like this:

You can find the code here.

In the next post, we are going to add functionality to the search button, so that when we press search it fetches search results from Github and display the search results on our TextView.

Longest Arithmetic Subsequence [Python]

Avin Sharma — Wed, 11 Mar 2020 00:00:00 +0000

Here's the Problem.

Naive approach - Exponential time

One of the ways we could solve this is to get all the sub-sequences and see if they are arithmetic. Pretty straight forward.

Now how do we generate all the subsequences? One of the ways could be like this:

def generate_subseq(seq):
    sequences = [[]]
    for num in seq:
        new_sequences = []
        for sub in sequences:
            copy = sub[:]
            copy.append(num)
            new_sequences.append(copy)
        sequences.extend(new_sequences)

    return sequences

seq = [1, 2, 3, 4]
print(generate_subseq(seq))

The time complexity of the above is O(2^n) since for every entry we can either select it or not select it.

And for every subsequence, we can check if its Arithmetic in O(n)

Can we do better?

Like in most cases if someone asks you this, chances are there is a better/faster way to solve the problem. Better time complexities are preferred over better space complexities.

Dynamic Programming - O(n^2)

The idea here is that from any index i, we find the difference between elements at index i and all the indexes before i, which gives us j -> 0 to i-1 [0, i).

Now that we have a difference diff, we also need to know if there is a subsequence that ends at index j with the difference diff. We need some way to store the information of all the subsequences that ends at j, to figure out if we are continuing a subsequence or starting a new one.

For example a new subsequence would be [5, 7], when we are at 7 we have a new subsequence that maintains the difference of 2 that ends at 7 or index 1.

A continuing subsequence would be [1, 3, 5, 7], where if we were at 7 and look at 5, we want to know that at 5 there is a subsequence of length 3 which maintains a difference of 2 so that we can add 7 to the previous subsequence and store the info.

Another thing to keep in mind would be that there could be multiple sequences with different differences that could end at a particular position in our original sequence or there could be shorter sequences with the same difference that ends at the same index, we keep the one with the maximum count.

Looking at the code below should give you greater clarity.

def longest_arithmetic_subsequence(A):
    n = len(A)
    if n < 3:
        return n

    counts = [{} for _ in A]
    max_count = 0

    for i in range(0, len(A)):
        for j in range(0, i):
            diff = A[i] - A[j]
            counts[i][diff] = max(counts[i].get(diff, 1), counts[j].get(diff, 1) + 1)
            max_count = max(max_count, counts[i][diff])

    return max_count

Use get() method of the dictionary to reduce lines of code. It reduces the volume by a lot.

Max Profit with K Transactions [Python]

Avin Sharma — Fri, 21 Feb 2020 00:00:00 +0000

A great question that I recently did on AlgoExpert, its the kind of question that checks you on how well you understand the concepts on dynamic programming.

The question is given an array of prices of a single stock over multiple days, find the maximum profit you can generate in k transactions. You can only buy one stock and cannot buy again before you sell it.

input: prices -> [2, 5, 7, 3, 10], k -> 2
output: 12 (7 - 2 (transaction1) + 10 - 3(transaction2))

The first thought that came to my mind was to use the concept of peaks and valleys(buying when the prices are the lowest and selling just before the prices start dropping again) and then choose k transactions with the highest profit, this does not work. Let's take the example above:

k = 1
possible transaction (1)-> buy at 2 sells at 5
possible transaction (2)-> buy at 3 sells at 10

Here according to our strategy the answer would be 7 but looking at the array again we could buy at 2 and sell at 10. The strategy above forces us to buy at the local minima and sell at the maxima, we dont get the see the bigger picture.

Dynamic Programming

The problem looks like it could be solved using dynamic programming, but what do you store here, since the question is about max profit a good guess would be to store max profit up to a certain point but how does that help us and how would we go about it. This is why this question is very trick although it's extremely simple to code.

The array given to us is the price of the stock at day d. So we create a table with dimensions d * (k+1), transactions from 0 to k(inclusive). The idea is to keep track of maximum possible profit at day d in t transactions.

   2 5 7 3 10
   ----------
0| 0 0 0 0 0
1| 0 3 5 5 8
2| 0 3 5 5 12

On any particular day, we can decide to SELL or carry over previous maximum profit, meaning no transaction occurred. In other words we decide if selling now is a profit or loss and act accordingly.

Now when we decide to sell, how do we decide which day should we have brought the stock on, this is where our table becomes useful. When we sell we get selling price - buying price the profit in the current transaction, + maximum profit in previous transactions on the day we bought the stock. If we sell at day d, buy at day x and we have k transactions we get prices[d] - prices[x] + max_profit[t-1][x], we want to maximize max(max_profit[t-1][x]), x->[0, d-1] and then finally compare it to maximum profit in k transactions at d-1 day which is max_profit[t][d-1].

def maxProfitWithKTransactions(prices, k):
    # Time: O(kn) | Space: O(n)
    prev_trans = [0 for _ in prices]

    for t in range(k):
        curr_trans = [0]
        max_diff = float('-inf')

        for i in range(1, len(prices)):
            max_diff = max(max_diff, prev_trans[i-1] - prices[i-1])
            curr_trans.append(max(curr_trans[i-1], prices[i] + max_diff))
        prev_trans = curr_trans[:]

    return curr_trans[-1]

Minimum Candies - Peaks and Vallies[Python]

Avin Sharma — Mon, 10 Feb 2020 00:00:00 +0000

Here’s the question on leetcode.

So we are given an array of ratings something like [1, 3, 2, 1, 2, 7, 5] and we need to handout as little candies as we can. So in my head(without any algorithm) the way I solved this was, well in 2 ways:

Going from left to right and changing the candies as required. It went like this:

['1']
[1, '2']
[1, 2, '1']
[1, 2, 1, '1'] -> [1, 2, '2', 1] ->[1, '3', 2, 1]
[1, 3, 2, 1, '2']
[1, 3, 2, 1, 2, '3']
[1, 3, 2, 1, 2, 3, '1']
Sum = 1 + 3 + 2 + 1 + 2 + 3 + 1 = 13

The problem which comes out pretty fast is that based on the rating you might increase the number of candies for a particular index but you might have to correct all the previous indexes as we see in the third line in the above example.

This is probably going to take O(N^2) Time

Starting from the smallest indexes and going outwards. This will take O(N) time.

Peaks and Valleys

The concept is to figure out when are we increasing/decreasing or finding out local minima and maxima. If we plot the above array we get a chart that looks like a mountain, hence the name peaks and valleys.

So finding these local minimums and expanding outwards feels a little involved.

Another way to solve this would be to go from left to right and update the number of candies for all the increasing ratings and similarly go right to left and do the same. We have to be careful about the peaks, where two rising sequences meet, we have to select the larger number of candies so that the peak is greater than both the sides.

def candy(ratings):
    candies = [1 for _ in ratings]

    for i in range(1, len(ratings)):
        if ratings[i] > ratings[i - 1]:
            candies[i] = max(candies[i], candies[i-1] + 1)

    for i in range(len(ratings) - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i+1] + 1)

    return sum(candies)

Minumum Number Of Jumps [Python]

Avin Sharma — Fri, 31 Jan 2020 00:00:00 +0000

Sample Input: [1, 5, 1, 1, 2, 1, 2]Sample Output: 2 (1 -> 5 -> 2), we jump from index 0 to 1 (1 -> 5) because we can jump 1 unit far from there and then we jump from index 1 to 6 (5 -> 2) because we can jump 5 units from there and we reach the end in 2 jumps.

O(n^2) Time | O(n) Space

My first thought was, this looks like a dynamic programming question. So I basically wanted to maintain an array of the same size as the input which would contain what is the minimum jumps to reach any particular index.

How do we do that? First we initialize the shortest array with infinity. The idea was to have two loops i(0 -> n-1) and j(0 -> i) and check if we could reach i from j and if we can, is shortest[j] + 1 < shortest[i]. If shortest[j] + 1 < shortest[i] then shortest[i] = shortest[j] + 1. After both the loops are done we return last element of the shortest array.

O(n) Time | O(1) Space

Yes this can be done in O(n) time and constant space. It is hard to come up with, but this kind of looks like one of those dynamic programming problems which could be done in a single pass.

Let's take a look at the problem once again. At any given index we have the maximum distance we could jump if we were standing there. So basically we might have two choices, to either continue the previous jump(let's say we were jumping from index 0 to 5, instead of stopping at 3 we continue our jump to 5) or to start a new jump from the current index.

So at any given point we have our maximum reach, and we keep updating our maximum reach as we keep moving forward. We also maintain a steps variable which is there to basically keep track of how many steps do we have left before we can commit to a jump. When steps reach 0, we assign the current maximum reach as the num of remaining steps because when steps reach 0 that means we are standing at that index and the largest jump from here would be the maximum reach we have been maintaining.

def minNumberOfJumps(array):
    # Time: O(n)
    # Space: O(1)

    if len(array) == 1:
        return 0

    max_reach_index = array[0]
    steps = array[0]
    jumps = 0

    for i in range(1, len(array) - 1):
        steps -= 1
        max_reach_index = max(max_reach_index, i + array[i])

        if steps == 0:
            jumps += 1
            steps = max_reach_index - i

    # Because we are going till the second last index
    # we will either have previous unfinished jump or
    # a new jump starts at second last index either way
    # we need to add a jump.
    jumps += 1

    return jumps